You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
- u v : ask for how many different integers that represent the weight of nodes there are on the path from u to v.
Input
In the first line there are two integers N and M. (N <= 40000, M <= 100000)
In the second line there are N integers. The i-th integer denotes the weight of the i-th node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains two integers u v, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.
Output
For each operation, print its result.
Example
Input: 8 2 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 5 7 8
Output: 4 4
题意：求两点间点权值的种类数量。
之前讲过了如何“皇室联邦分块”，由于此题没有要求在线，就先分块，然后莫队就行了。
每次转移的时候怕出错，就干脆vis标记即可。
此题还有很多在线的做法。强得不行。。。ORZ
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=40010; const int maxm=100010; int n,m,group[maxn]; struct in { int x; int y; int id; friend bool operator< (in a,in b) { return group[a.x]!=group[b.x]?group[a.x]<group[b.x]:group[a.y]<group[b.y]; } }q[maxm]; struct Solve { int maxi; int Next[maxn<<1],Laxt[maxn],To[maxn<<1],cnt,delta; int num[maxn],dep[maxn],anc[maxn][21],w[maxn],wx[maxn]; int B,stc[maxn],top,tot,ans[maxm],vis[maxn]; int swap(int &u,int &v) { u^=v;v^=u;u^=v;} int read() { int res=0;bool t=false; char c=getchar(); while(c>'9'||c<'0') { if(c=='-') t=true; c=getchar();} while(c<='9'&&c>='0') { res=(res<<1)+(res<<3)+c-'0';c=getchar();} if(t) return -res; return res; } void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } void init() { int u,v; B=sqrt(n); for(int i=1;(1<<i)<=n;i++) maxi=i; for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) wx[i]=w[i]; sort(wx+1,wx+n+1); int tt=unique(wx+1,wx+n+1)-(wx+1); for(int i=1;i<=n;i++) w[i]=lower_bound(wx+1,wx+tt+1,w[i])-wx; for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dep[1]=1; dfs(1); while(top) group[stc[top--]]=tot;//最后剩余部分莫忘liao。 for(int i=1;i<=m;i++) { q[i].id=i, scanf("%d%d",&q[i].x,&q[i].y); if(group[q[i].x]<group[q[i].y]) swap(q[i].x,q[i].y);//稍微调整一下，可能会优化。 } sort(q+1,q+m+1); get_LCA(); } void dfs(int u) { int Now=top; for(int i=Laxt[u];i;i=Next[i]) if(!dep[To[i]]){ anc[To[i]][0]=u; dep[To[i]]=dep[u]+1; dfs(To[i]); if(top-Now>=B) { ++tot; while(top!=Now) group[stc[top--]]=tot; } } stc[++top]=u; } void get_LCA() { for(int i=1;i<=maxi;i++) for(int j=1;j<=n;j++) anc[j][i]=anc[anc[j][i-1]][i-1]; } int LCA(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=maxi;i>=0;i--) if(dep[anc[u][i]]>=dep[v]) u=anc[u][i]; if(u==v) return u; for(int i=maxi;i>=0;i--){ if(anc[u][i]!=anc[v][i]){ u=anc[u][i]; v=anc[v][i]; } } return anc[u][0]; } void trans(int &u) { if(vis[u]) //已被记录，则本次去掉此点 { if(--num[w[u]] == 0) delta--; } else if(++num[w[u]] == 1) delta++; vis[u] ^= 1; u=anc[u][0]; } void solve() { int su=1,sv=1; delta=0; for(int i = 1; i <= m; i++) { int tu=q[i].x,tv=q[i].y; int lca=LCA(su, tu);//两点朝lca移动，处理路径上的点 while(su!=lca) trans(su); while(tu!=lca) trans(tu); lca=LCA(sv,tv); while(sv!=lca) trans(sv); while(tv!=lca) trans(tv); su=q[i].x,sv=q[i].y; lca=LCA(sv, su); ans[q[i].id]=delta+(!num[w[lca]]);//对lca特殊处理 } for(int i=1;i<=m;i++) printf("%d ",ans[i]); } }Tree; int main() { scanf("%d%d",&n,&m); Tree.init(); Tree.solve(); return 0; }