我现在爱死树链剖分了
具体分析的话在洛谷blog里
这里只是想放一下改完之后的代码
多了一个son数组少了一个for
少了找size最大的儿子的for
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100100; int n, q, head[N], cnt, dad[N], top[N], size[N], deep[N], son[N]; struct edge{ int next, to; }e[N << 1]; int read() { int s = 0, w = 1; char ch = getchar(); while(!isdigit(ch)) {if(ch == '-') w = -1;ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();} return s * w; } void add(int x, int y) { e[++cnt].next = head[x]; e[cnt].to = y; head[x] = cnt; } void dfs(int now) { size[now] = 1; deep[now] = deep[dad[now]] + 1; for(int i = head[now]; i; i = e[i].next) if(e[i].to != dad[now]) { dad[e[i].to] = now, dfs(e[i].to), size[now] += size[e[i].to]; if(size[e[i].to] > size[son[now]]) son[now] = e[i].to; } } void dfs1(int now) { if(!top[now]) top[now] = now; if(son[now]) top[son[now]] = top[now], dfs1(son[now]); for(int i = head[now]; i; i = e[i].next) if(e[i].to != dad[now] && e[i].to != son[now]) dfs1(e[i].to); } int lca(int x, int y) { while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x, y); x = dad[top[x]]; } return deep[x] > deep[y] ? y : x; } int main () { n = read();q = read(); for(int i = 1, u, v; i < n; i++) { u = read();v = read(); add(u, v), add(v, u); } dfs(1); dfs1(1); for(int i = 1, a, b, c, d; i <= q; i++) { a = read(), b = read(), c = read(), d = read(); int fir = max(deep[lca(a, b)], deep[lca(c, d)]); int sec = max(max(deep[lca(a, c)], deep[lca(a, d)]), max(deep[lca(b, c)], deep[lca(b, d)])); if(sec >= fir) puts("Y"); else puts("N"); } return 0; }
谢谢收看， 祝身体健康！