题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3757
数据传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/3757.rar
树上莫队的模板题!
真的是好板,只要会树分块就可以写辣!
然而树上莫队有几个地方必须要注意:
1.排序的时候必须以一个点的所在树块的编号为第一关键字,然后第二关键字搞成另一点的DFS序
2.最好把每个询问的两个点中DFS较大的作为第二个点
以上这么做为什么会极大的影响速度并不是太清楚 ╮(╯▽╰)╭ 不过效果真的很好
还有不会的同学,出门左拐去找PoPoQQQ吧:http://blog.csdn.net/popoqqq/article/details/41479829
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 50000+9; const int M = 100000+9; int head[N],to[M],nxt[M],n,m,col[N],stk[M],top,LIM,dfs_num[M]; int fa[N][17],dep[N],cnt[N],ans,num[N],vout[M],sta[N]; struct Query{ int u,v,a,b,id; bool operator < (const Query &B) const { return num[u] < num[B.u] || (num[u] == num[B.u] && dfs_num[v] < dfs_num[B.v]); } }query[M]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } void DFS(int w, int f, int bot) { static int block_cnt = 0; static int dfs_cnt = 0; dfs_num[w] = ++dfs_cnt; fa[w][0] = f; dep[w] = dep[f] + 1; for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { DFS(to[i],w,top); if (top - bot >= LIM) { block_cnt++; while (top > bot) { num[stk[top--]] = block_cnt; } } } } stk[++top] = w; while (!w && top) { num[stk[top--]] = block_cnt; } } inline void update(int id, bool delta) { if (cnt[id] == 1 && !delta) ans--; else if (!cnt[id] && delta) ans++; cnt[id] += delta?1:-1; } inline int LCA(int x, int y) { if (dep[x] < dep[y]) swap(x,y); for (int i=16;~i;i--) { if (dep[fa[x][i]] >= dep[y]) { x = fa[x][i]; } } if (x == y) return x; for (int i=16;~i;i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } inline void move(int &w, int pur) { int lca = LCA(w, pur); for (int i=w;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1); for (int i=pur;i!=lca;i=fa[i][0]) update(col[i], sta[i] ^= 1); w = pur; } inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } int main(){ int size = 128 << 20; char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); n = read(); m = read(); LIM = sqrt(n) + 1; for (int i=1;i<=n;i++) col[i] = read(); for (int i=1;i<=n;i++) Add_Edge(read(), read()); DFS(0,0,0); for (int i=1;i<=16;i++) { for (int j=0;j<=n;j++) { fa[j][i] = fa[fa[j][i-1]][i-1]; } } for (int i=1;i<=m;i++) { query[i].id = i; query[i].u = read(); query[i].v = read(); query[i].a = read(); query[i].b = read(); if (dfs_num[query[i].u] > dfs_num[query[i].v]) { swap(query[i].u, query[i].v); } } sort(query+1, query+1+m); for (int i=1,p1=0,p2=0;i<=m;i++) { move(p1, query[i].u); move(p2, query[i].v); int lca = LCA(query[i].v, query[i].u); update(col[lca], sta[lca] ^= 1); vout[query[i].id] = ans; if (query[i].a != query[i].b && cnt[query[i].a] && cnt[query[i].b]) vout[query[i].id]--; update(col[lca], sta[lca] ^= 1); } for (int i=1;i<=m;i++) { printf("%d\n",vout[i]); } return 0; }