那天贼累就请了一个下午+晚上的假，九点多发现Hank_o大佬居然没有写题，只跟他差一题，就去切了题水题，然后来做这题看似很水的题。
很容易看出来是dfs序+线段树（树状数组那时候想了想好像用不了，现在忘了）
然后我写的线段树T成谜。无语。
好像现在这个就叫可持久化标记（直接看代码都看懂了，应该算是个小技巧吧），学了学。
不知不觉十一点半（捂脸，我好菜
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,next; }a[210000];int len,last[110000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int z,l[110000],r[110000],dep[110000]; void dfs(int x,int f) { l[x]=++z; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f) dep[y]=dep[x]+1, dfs(y,x); } r[x]=z; } struct trnode { int l,r,lc,rc,id; }tr[2100000];int trlen; void bt(int l,int r) { trlen++;int now=trlen; tr[now].l=l;tr[now].r=r; tr[now].id=1; if(l<r) { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); } } void change(int now,int l,int r,int id) { if(tr[now].l==l&&tr[now].r==r) { if(dep[tr[now].id]<dep[id])tr[now].id=id; return ; } int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) change(lc,l,r,id); else if(mid+1<=l)change(rc,l,r,id); else change(lc,l,mid,id), change(rc,mid+1,r,id); } int findmax(int now,int p) { if(tr[now].l==tr[now].r)return tr[now].id; int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; int t1=tr[now].id,t2; if(p<=mid)t2=findmax(lc,p); else t2=findmax(rc,p); if(dep[t1]<dep[t2])swap(t1,t2); return t1; } char ss[10]; int main() { int n,m,x,y; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } z=0;dep[1]=1;dfs(1,0); trlen=0;bt(1,n); while(m--) { scanf("%s%d",ss+1,&x); if(ss[1]=='Q')printf("%d ",findmax(1,l[x])); else change(1,l[x],r[x],x); } return 0; }