LCA

题意： 有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。

题目链接 题意： # 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： # 暴力即可orz(数据是真的水啊。

题目链接 题意： # 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： # LCA还是一下就能想到的，rmq+dfs在线求。

题目链接 题意：求一个BST中某两个节点LCA…. 思路：卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月21日 星期六 14时44分39秒 4File Name :code/zoj/3195.cpp 5************************************************ */ 6 7 8 9#include <cstdio> 10#include <cstring> 11#include <iostream> 12#include <algorithm> 13#include <vector> 14#include <queue> 15#include <set> 16#include <map> 17#include <string> 18#include <cmath> 19#include <cstdlib> 20#include <ctime> 21#define fst first 22#define sec second 23#define lson l,m,rt<<1 24#define rson m+1,r,rt<<1|1 25#define ms(a,x) memset(a,x,sizeof(a)) 26typedef long long LL; 27#define pi pair < int ,int > 28#define MP make_pair 29 30using namespace std; 31const double eps = 1E-8; 32const int dx4[4]={1,0,0,-1}; 33const int dy4[4]={0,-1,1,0}; 34const int inf = 0x3f3f3f3f; 35const int N=5E4+7; 36int n,m; 37vector < pi > edge[N]; 38int q; 39int in[N]; 40int E[2*N],R[2*N],dis[N],depth[2*N]; 41int p; 42int dp[2*N][20]; 43void dfs( int u,int dep,int d,int pre) 44{ 45 46 // cout<<"u:"<<u<<" dep:"<<dep<<" d:"<<d<<endl; 47 p++; 48 E[p] = u; 49 depth[p] = dep; 50 R[u] = p ; 51 dis[u] = d; 52 53 54 int siz = edge[u].size(); 55 for ( int i = 0 ; i < siz ; i++) 56 { 57 int v = edge[u][i].fst; 58 if (v==pre) continue; 59 dfs(v,dep+1,d+edge[u][i].sec,u); 60 61 p++; 62 E[p] = u; 63 depth[p] = dep; 64 } 65} 66 67 68 69int _min( int l,int r) 70{ 71 if (depth[l]<depth[r]) return l; 72 return r; 73} 74void rmq_init() 75{ 76 for ( int i = 1 ; i <= 2*n+2 ; i++) dp[i][0] = i; 77 78 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 79 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 80 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 81} 82 83int rmq_min( int l,int r) 84{ 85 if (l>r) swap(l,r); 86 int k = 0 ; 87 while (1<<(k+1)<=r-l+1) k++; 88 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 89} 90int solve (int x,int y) 91{ 92 int LCA = E[rmq_min(R[x],R[y])]; 93 int res = dis[x] + dis[y] - 2 * dis[LCA]; 94 return res; 95} 96int main() 97{ 98 #ifndef ONLINE_JUDGE 99 freopen("code/in.txt","r",stdin); 100 #endif 101 102 ms(in,0); 103 bool ok = false; 104 while (~scanf("%d",&n)){ 105 if (ok) puts(""); 106 ok = true; 107 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 108 for ( int i = 1 ; i <= n-1 ; i++) 109 { 110 int u,v,w; 111 scanf("%d%d%d",&u,&v,&w); 112 edge[u].push_back(make_pair(v,w)); 113 edge[v].push_back(make_pair(u,w)); 114 } 115 116 117 p = 0 ; 118 dfs(0,0,0,-1); 119 rmq_init(); 120 121 scanf("%d",&q); 122 while (q--) 123 { 124 int x,y,z; 125 scanf("%d%d%d",&x,&y,&z); 126 int ans = solve(x,y)+solve(x,z)+solve(y,z); 127 printf("%d\n",ans/2); 128 } 129 } 130 131#ifndef ONLINE_JUDGE 132 fclose(stdin); 133#endif 134 return 0; 135}

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是：添加虚点！ 最最重要的一点是：添加虚点！ 最最重要的一点是：添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月19日 星期四 15时44分12秒 4File Name :code/poj/1470.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=905; 34int n; 35vector <int> edge[N]; 36int in[N]; 37int E[2*N],R[2*N]; 38int depth[2*N]; 39int p; 40int dp[2*N][12]; 41int cnt[N]; 42void dfs( int u,int dep) 43{ 44 p++; 45 E[p] = u ; 46 depth[p] = dep; 47 R[u] = p; 48 int siz = edge[u].size(); 49 for ( int i = 0 ; i < siz ; i ++) 50 { 51 int v = edge[u][i]; 52 53 dfs(v,dep+1); 54 p++; 55 E[p] = u; 56 depth[p] = dep; 57 } 58} 59 60int _min( int l,int r) 61{ 62 if (depth[l]<depth[r]) return l; 63 return r; 64} 65void rmq_init() 66{ 67 for ( int i = 1 ; i <=2*n+2 ; i++) dp[i][0] = i; 68 69 for ( int j = 1 ; (1<<j) <= 2*n+2 ; j++) 70 for ( int i = 1 ; i + (1<<j)-1 <= 2*n+2 ; i++) 71 dp[i][j] = _min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 72} 73 74int rmq_min( int l,int r) 75{ 76 if (l>r) swap(l,r); 77 int k = 0; 78 while (1<<(k+1) <= r-l+1) k++; 79 return _min(dp[l][k],dp[r-(1<<k)+1][k]); 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 while (scanf("%d",&n)!=EOF) 88 { 89 ms(in,0); 90 for ( int i = 1 ; i <= n ; i++) edge[i].clear(); 91 for ( int i = 1 ; i <= n ; i++) 92 { 93 char ch[5]; 94 int x,num; 95 scanf("%d%2s%d%1s",&x,ch,&num,ch); 96// cout<<"x:"<<x<<" num:"<<num<<endl; 97 98 for ( int i = 1 ; i <= num ; i++) 99 { 100 int y; 101 scanf("%d",&y); 102 edge[x].push_back(y); 103 in[y]++; 104// cout<<"y:"<<y<<endl; 105 } 106 } 107 108 int root ; 109 for ( int i = 1 ; i <= n ; i++) if (in[i]==0) root = i ; 110// cout<<"root:"<<root<<endl; 111 p = 0; 112 dfs(root,0); 113 rmq_init(); 114 115 ms(cnt,0); 116 117 int q; 118 scanf("%d",&q); 119// cout<<"q:"<<q<<endl; 120 while (q--) 121 { 122 char ch[5]; 123 int x,y; 124 scanf("%1s%d%d%1s",ch,&x,&y,ch); 125 int LCA = E[rmq_min(R[x],R[y])]; 126// cout<<"x:"<<x<<" y:"<<y<<" LCA:"<<LCA<<endl; 127 cnt[LCA]++; 128 } 129// cout<<"n:"<<n<<endl; 130 for ( int i = 1 ; i <= n ; i++) 131 { 132// cout<<"cnt[i]:"<<cnt[i]<<endl; 133 if (cnt[i]==0) continue; 134 printf("%d:%d\n",i,cnt[i]); 135 } 136 } 137 138 #ifndef ONLINE_JUDGE 139 fclose(stdin); 140 #endif 141 return 0; 142}

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。

题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路： dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];