Description
给您一颗树，每个节点有个初始值。 现在支持以下两种操作： 1. C i x(0<=x<2^31) 表示将i节点的值改为x。 2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点。 Input
第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数。 下面一行N个整数，表示初始时每个节点的初始值。 接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）。 接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。 Output
对于每个Q输出单独一行表示所求的答案。 Sample Input
5 6
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 3 40
C 1 40
Q 2 3 40
Q 4 5 30
C 3 10
Q 4 5 30 Sample Output
0
1
1
0
出题人不要求强制在线就可以乱搞了。。 离散化肯定是要的。。 想我这种垃圾就只会树剖，就剖一下，对于每一个x动态开点建线段树就好了 就是把普通树剖传多一个树根编号而已。。改一下动态开点。。 时间复杂度 O(q∗logn∗logn) 其实看起来我觉得有点大。。 然而跑得挺快的
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; const int N=100005; const int Q=200005; int n,q; int a[N]; int A[N+Q],Cnt=0; struct qq { int x,y,last; }e[N*2];int num,last[N]; void init (int x,int y) { num++; e[num].x=x;e[num].y=y; e[num].last=last[x]; last[x]=num; } struct qy{int i,j,x;}ask[Q];//询问 void Init () { num=0;memset(last,-1,sizeof(last)); scanf("%d%d",&n,&q); for (int u=1;u<=n;u++) { scanf("%d",&a[u]); A[++Cnt]=a[u]; } for (int u=1;u<n;u++) { int x,y; scanf("%d%d",&x,&y); init(x,y);init(y,x); } for (int u=1;u<=q;u++) { char ss[N]; scanf("%s",ss); if (ss[0]=='C')//修改 { scanf("%d%d",&ask[u].i,&ask[u].x); ask[u].j=-1; A[++Cnt]=ask[u].x; } else scanf("%d%d%d",&ask[u].i,&ask[u].j,&ask[u].x); } } int tot[N],f[N],dep[N],son[N]; void dfs (int x,int fa) { f[x]=fa;tot[x]=1; for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; if (y==fa) continue; dep[y]=dep[x]+1;dfs(y,x); tot[x]+=tot[y]; if (tot[son[x]]<tot[y]) son[x]=y; } } int ys[N],top[N],num1; void dfs1 (int x,int y) { top[x]=y;ys[x]=++num1; if (son[x]!=0) dfs1(son[x],y); for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; if (y==son[x]||y==f[x]) continue; dfs1(y,y); } } int Find (int x) { int l=1,r=Cnt; while (l<=r) { int mid=(l+r)>>1; if (A[mid]==x) return mid; if (A[mid]>x) r=mid-1; else l=mid+1; } return 0;//防止不存在的情况 } int root[N+Q],ooo=0; struct qt { int s1,s2; int c; }s[(N+Q)*20*2]; void change (int &now,int l,int r,int x,int y)//这条边变一下 { if (now==0) now=++ooo; if (l==r) { s[now].c+=y; return ; } int mid=(l+r)>>1; if (x<=mid) change(s[now].s1,l,mid,x,y); else change(s[now].s2,mid+1,r,x,y); s[now].c=s[s[now].s1].c+s[s[now].s2].c; } void prepare ()//各种预处理 { sort(A+1,A+1+Cnt); /*for (int u=1;u<=Cnt;u++) printf("%d ",A[u]); printf("\n");*/ int ccnt=1; for (int u=2;u<=Cnt;u++) if (A[u]!=A[ccnt]) A[++ccnt]=A[u]; Cnt=ccnt; // for (int u=1;u<=Cnt;u++) printf("%d ",A[u]); dep[1]=1;dfs(1,0); num1=0;dfs1(1,1); for (int u=1;u<=n;u++) change(root[Find(a[u])],1,num1,ys[u],1); } int get (int now,int l,int r,int L,int R) { //printf("now:%d c:%d l:%d r:%d L:%d R:%d\n",now,s[now].c,l,r,L,R); if (now==0) return 0; if (l==L&&r==R) return s[now].c; if (s[now].c==0)//以前荒废的 return 0; int s1=s[now].s1,s2=s[now].s2; int mid=(l+r)>>1; if (R<=mid) return get(s1,l,mid,L,R); else if (L>mid) return get(s2,mid+1,r,L,R); else return get(s1,l,mid,L,mid)+get(s2,mid+1,r,mid+1,R); } int get_ans (int x,int y,int z) { if (z==0) return 0; // printf("%d %d %d\n",x,y,z); int tx=top[x],ty=top[y]; if (dep[tx]>dep[ty]) {swap(tx,ty);swap(x,y);} int ans=0; while (tx!=ty) { ans=ans+get(root[z],1,num1,ys[ty],ys[y]); y=f[ty];ty=top[y]; if (dep[tx]>dep[ty]) {swap(tx,ty);swap(x,y);} } if (dep[x]>dep[y]) swap(x,y); ans=ans+get(root[z],1,num1,ys[x],ys[y]); return ans; } void solve () { for (int u=1;u<=q;u++) { if (ask[u].j==-1)//是一个修改操作 { change(root[Find(a[ask[u].i])],1,num1,ys[ask[u].i],-1);//这个点在x这颗树上不见了 a[ask[u].i]=ask[u].x; change(root[Find(a[ask[u].i])],1,num1,ys[ask[u].i],1);//这个点在x这颗树上出现了 } else { //printf("%d %d\n",ask[u].x,Find(ask[u].x)); printf("%d\n",get_ans(ask[u].i,ask[u].j,Find(ask[u].x))); } } } int main() { Init(); prepare(); solve(); return 0; }