hdu3974 发表于 2018-04-08 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:hdu3974 题解 可能会有人想要用不压缩的并查集去做,显然不可以。 正解是用线段树维护时间戳,给x分配任务y实际上就是把in[x]—out[x]这段置为y 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<vector>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define lson o<<1,l,mid#define rson o<<1|1,mid+1,rusing namespace std;const int N=1e5;int rt[N<<2],in[N],out[N],n,m,cnt,T;vector<int> g[N],em[N];char c;void init(){rep(i,1,n){g[i].clear();em[i].clear();}}inline void dfs(int x){ in[x]=++cnt; for(int i=0;i<g[x].size();++i)dfs(g[x][i]); out[x]=cnt;}inline void pushdown(int o){rt[o<<1]=rt[o<<1|1]=rt[o];rt[o]=-1;}inline void build(int o,int l,int r){ rt[o]=-1; if(l==r)return ; int mid=l+r>>1; build(lson); build(rson);}inline void update(int o,int l,int r,int L,int R,int x){ if(L==l&&R==r){rt[o]=x;return;} if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; if(R<=mid)update(lson,L,R,x); else if(L>mid)update(rson,L,R,x); else { update(lson,L,mid,x); update(rson,mid+1,R,x); }}inline int query(int o,int l,int r,int x){ if(l==r)return rt[o]; if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; if(x<=mid)return query(lson,x); else return query(rson,x);}int main(){ ios::sync_with_stdio(false); cin>>T; rep(cs,1,T){ cnt=0; cin>>n; build(1,1,n); init(); rep(i,1,n-1){ int x,y; cin>>x>>y; g[y].push_back(x); em[x].push_back(y); } rep(i,1,n)if(em[i].size()==0)dfs(i); cin>>m; cout<<"Case #"<<cs<<":"<<endl; while(m--){ char c;cin>>c; if(c=='C'){ int x;cin>>x; cout<<query(1,1,n,in[x])<<endl; } else {int x,y;cin>>x>>y; update(1,1,n,in[x],out[x],y); } } } return 0;}