【标签】离散化，数据结构，分治，图论
【题意】
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 perfrom 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.
【分析】
首先离散化，把w转化一下，开始看到integer以为是-32768和32767间的整数，直接开桶存储，然后就悲剧地挂掉了…
然后DFS一遍，lst保存入和出的总序列，in保存第i个点入的编号，out保存出的编号
对于路径：树上倍增求LCA
对于问题：树上莫队。
（1）若x=y答案就是1
（2）若LCA(x,y)=x或y则左端点为min(in[x],in[y])，右端点为max(in[x],in[y])
（3）若都不同则左端点为min(out[i],out[j])，，右为max(in[i],in[j])，这是可以证明的。
然后用莫队算法排序预处理，直接暴力，暴力时要用has[N]表示这个节点有没有被访问，开v[N]存储每个元素有多少个，然后访问一个节点has[N]就 xor 1。
注意要按照题目的顺序输出答案，开ans记录每个答案就是了
下面的代码有相关易错点…
【实现】
#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;const int N=40001;const int M=161121;const int K=16;struct R{int d,id;}rk[N];int n,m,w[N];struct G{int v,nxt;}map[N<<1];int tot,hd[N];int in[N],out[N],lst[N<<1],num;int pre[K+2][N],dep[N];struct Q{int l,r,anc,id;}q[M];int v[N],unit,res,l,r,has[N],ans[M];//注意ans的数据范围，为询问的个数 inline void ins(int u,int v){map[++tot].v=v;map[tot].nxt=hd[u];hd[u]=tot;}void DFS(int now,int high){dep[now]=high;in[now]=++num;lst[num]=now;for (int k=hd[now];k;k=map[k].nxt)if (!dep[map[k].v]){DFS(map[k].v,high+1);pre[0][map[k].v]=now;}out[now]=++num;lst[num]=now;}inline int cmp1(R a,R b){return a.d<b.d;}void init(void){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&w[i]);int tmp,cnt;for (int i=1;i<=n;i++) rk[i].d=w[i],rk[i].id=i;sort(rk+1,rk+n+1,cmp1);tmp=rk[1].d,w[rk[1].id]=cnt=1;for (int i=2;i<=n;i++){if (tmp^rk[i].d) tmp=rk[i].d,cnt++;w[rk[i].id]=cnt;}int x,y;for (int i=1;i<n;i++){scanf("%d%d",&x,&y);ins(x,y),ins(y,x);}pre[0][1]=1;DFS(1,1);for (int i=1;i<=K;i++)for (int j=1;j<=n;j++)pre[i][j]=pre[i-1][pre[i-1][j]];}inline int cmp(Q a,Q b){return a.l/unit!=b.l/unit?a.l/unit<b.l/unit:a.r<b.r;}inline int min(int i,int j){return i<j?i:j;}inline int max(int i,int j){return i>j?i:j;}inline int LCA(int x,int y){if (dep[x]>dep[y]) x^=y^=x^=y;for (int i=K;i+1;i–)if (dep[y]-dep[x]>=1<<i) y=pre[i][y];if (x==y) return x;//注意特判x=y时的LCA就是x=y for (int i=K;i+1;i–)if (pre[i][x]^pre[i][y])x=pre[i][x],y=pre[i][y];return pre[0][x];}inline void solve(int i)//"有无"时的写法 {if (has[lst[i]]){v[w[lst[i]]]–;if (!v[w[lst[i]]]) res–;has[lst[i]]=0;}else{if (!v[w[lst[i]]]) res++;v[w[lst[i]]]++;has[lst[i]]=1;}}void work(void){int x,y;unit=(int)sqrt(num);//num instead of n for (int i=1;i<=m;i++) {scanf("%d%d",&x,&y);q[i].id=i;if (x==y) q[i].anc=-1;else{q[i].anc=LCA(x,y);if (q[i].anc!=x&&q[i].anc!=y){q[i].l=min(out[x],out[y]);q[i].r=max(in[x],in[y]);}else{q[i].l=min(in[x],in[y]);q[i].r=max(in[x],in[y]);}//（1）相同（2）有1个为LCA：两个in（3） 都不同：max(in)&&min(out)}}sort(q+1,q+m+1,cmp);//注意用id弄到ans，不能直接输出l=1,r=0;for (int i=1;i<=m;i++)if (q[i].anc==-1) ans[q[i].id]=1;else{for (;l<q[i].l;l++) solve(l);for (;q[i].l<l;l–)solve(l-1);for (;r<q[i].r;r++) solve(r+1);for (;q[i].r<r;r–) solve(r);if (lst[q[i].l]==q[i].anc||lst[q[i].r]==q[i].anc)//注意加上lstans[q[i].id]=res;else{solve(in[q[i].anc]);ans[q[i].id]=res;solve(in[q[i].anc]);}}for (int i=1;i<=m;i++) printf("%d\n",ans[i]);}int main(void){init();work();return 0;}
【小结】
(1) 树上倍增
(2) 树上莫队"有无"的写法，注意3种情况的分类讨论
(3) 排序后的结果要开ans[M]按序输出
(4) Integer是整数的意思，不是-32768–32767。。。
活在当下，别在怀念过去或者憧憬未来中浪费掉你现在的生活。
