【倍增求lca】仓鼠找sugar

洛谷P3398 仓鼠找sugar

倍增求lca可做qwq

题目大意，只要两条路径有重合之处便输出“Y”;

几点小思路：

如果一对点的LCA的深度比另外一对点中任意一个点的深度都要深，不可能相遇，输出N。
如果一对点的起点or终点与另一对点的起点or终点相同，可能相遇，输出Y。
如果两对点的LCA相同，可能相遇，输出Y。
设r1 = lca(a,b)， r2 = lca(c,d) 且dep[r1] < dep[r2] ，则若两条路径有重合， lca(r1,c) == r1 || lca(r1,d) == r1; 反之亦然。

代码君qwq

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<iostream>
  4 using namespace std;
  5 const int sz = 100010;
  6 int n, q, log2n;
  7 int num = 0, head[sz], jump[sz][20], dep[sz];
  8 struct node {
  9     int nxt, to;
 10 }e[sz<<1];
 11 inline int read() {
 12     int x = 0 , f = 1;char ch = getchar();
 13     while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
 14     while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
 15     return x * f;
 16 }
 17 void add(int from, int to) {
 18     e[++num].nxt = head[from];
 19     e[num].to = to;
 20     head[from] = num;
 21 }
 22 void dfs(int u) {
 23     for(int i = head[u]; i; i = e[i].nxt) {
 24         int v = e[i].to;
 25         if(v != jump[u][0]) {
 26             jump[v][0] = u;
 27             dep[v] = dep[u]+1;
 28             dfs(v);
 29         }
 30     }
 31 }
 32 void init() {
 33     for(int i = 1; i <= log2n; i++) 
 34         for(int j = 1; j <= n; j++) 
 35             jump[j][i] = jump[jump[j][i-1]][i-1];
 36 }
 37 int lca(int x, int y) {
 38     if(dep[x]<dep[y]) swap(x,y);
 39     int t = dep[x] - dep[y];
 40     for(int i = 0; (1<<i) <= n; i++) {
 41         if(t&(1<<i)) x = jump[x][i];
 42     }
 43     if(x == y) return x;
 44     for(int i = log2n; i >= 0; i--) {
 45         if(jump[x][i] != jump[y][i]) {
 46             x = jump[x][i];
 47             y = jump[y][i];
 48         }
 49     }
 50     return jump[x][0];
 51 }
 52 int main() {
 53     n = read(), q = read();
 54     log2n = log(n)/log(2)+1;
 55     for(int i = 1; i < n; i++) {
 56         int x = read(), y = read();
 57         add(x, y);
 58         add(y, x);
 59     }
 60     int s = 1;
 61     dep[s] = 1;
 62     jump[s][0] = 0;
 63     dfs(s);
 64     init();
 65     for(int i = 1; i <= q; i++) {
 66         int a = read(), b = read(), c = read(), d = read();
 67         if(a==c||a==d||b==c||b==d) {
 68             cout<<"Y"<<endl;
 69             continue;
 70         }
 71         else {
 72             int r1 = lca(a,b);
 73             int r2 = lca(c,d);
 74             if(r1 == r2) {
 75                 cout<<"Y"<<endl;
 76                 continue;
 77             }
 78             if(dep[r1]>dep[c] && dep[r1]>dep[d]) {
 79                 cout<<"N"<<endl;
 80                 continue;
 81             }
 82             if(dep[r2]>dep[a] && dep[r2]>dep[b]) {
 83                 cout<<"N"<<endl;
 84                 continue;
 85             }
 86             if(dep[r1] > dep[r2]) {
 87                 if(lca(r1,c) == r1 || lca(r1,d) == r1) {
 88                     cout<<"Y"<<endl;
 89                     continue;
 90                 } 
 91                 else {
 92                     cout<<"N"<<endl;
 93                     continue;
 94                 }
 95             }
 96             else {
 97                 if(lca(r2,a) == r2 || lca(r2,b) == r2) {
 98                     cout<<"Y"<<endl;
 99                     continue;
100                 } 
101                 else {
102                     cout<<"N"<<endl;
103                     continue;
104                 }
105             } 
106          }
107     }
108     return 0;
109 }

　　　加个快读能快200+ms哦

总之岁月漫长，然而值得期待。