Qtree3

打完以后才发现写复杂了……算了懒得改了
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 int dep[100005],fa[100005][20],size[100005],wson[100005],vis[100005],sid[100005],tid[100005];
  5 int n,m,t1,t2,t3,t4,ind,top[100005],a[100005];
  6 
  7 vector <int> g[100005];
  8 
  9 void dfs1(int p) {
 10     size[p]=1;
 11     vis[p]=1;
 12     for(int i=0;i<g[p].size();i++) {
 13         if(vis[g[p][i]]) continue;
 14         dep[g[p][i]]=dep[p]+1;
 15         fa[g[p][i]][0]=p;
 16         dfs1(g[p][i]);
 17         size[p]+=size[g[p][i]];
 18         if(size[g[p][i]]>size[wson[p]]) wson[p]=g[p][i];
 19     }
 20 }
 21 
 22 void dfs2(int p) {
 23     vis[p]=1;
 24     sid[p]=++ind;
 25     tid[ind]=p;
 26     if(wson[p]) {
 27         top[wson[p]]=top[p];
 28         dfs2(wson[p]);
 29     }
 30     for(int i=0;i<g[p].size();i++) {
 31         if(vis[g[p][i]]) continue;
 32         top[g[p][i]]=g[p][i];
 33         dfs2(g[p][i]);
 34     }
 35 }
 36 
 37 void lca_presolve() {
 38     for(int i=1;i<=17;i++) 
 39         for(int j=1;j<=n;j++) 
 40             fa[j][i]=fa[fa[j][i-1]][i-1];
 41 }
 42 
 43 int lca(int p,int q) {
 44     if(dep[p]<dep[q]) swap(p,q);
 45     for(int i=17;i>=0;i--) if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
 46     for(int i=17;i>=0;i--) if(fa[p][i]-fa[q][i]) p=fa[p][i], q=fa[q][i];
 47     if(p-q) p=fa[p][0], q=fa[q][0];
 48     return max(p,q);
 49 }
 50 
 51 void pushup(int p){
 52     if(a[p*2]) a[p]=a[p*2];
 53     else a[p]=a[p*2+1];
 54 }
 55 
 56 void modify(int p,int l,int r,int pos) {
 57     if(l==r) {
 58         a[p]=a[p]?0:l;
 59         return;
 60     }
 61     if(pos<=(l+r)/2) modify(p*2,l,(l+r)/2,pos);
 62     else modify(p*2+1,(l+r)/2+1,r,pos);
 63     pushup(p);
 64 }
 65 
 66 int query(int p,int l,int r,int ql,int qr) {
 67     if(l>qr||r<ql) return 0;
 68     if(l>=ql&&r<=qr) return a[p];
 69     int q0=query(p*2,l,(l+r)/2,ql,qr);
 70     if(q0) return q0;
 71     else return query(p*2+1,(l+r)/2+1,r,ql,qr);
 72 }
 73 
 74 void tmodify(int pos) {
 75     modify(1,1,n,sid[pos]);
 76 }
 77 
 78 int lquery_upward(int anc,int son) {
 79     int ans=0;
 80     while(dep[top[son]]>dep[anc]) {
 81         ans=query(1,1,n,sid[top[son]],sid[son]);
 82         son=fa[top[son]][0];
 83         if(ans) return ans;
 84     }
 85     return query(1,1,n,sid[anc],sid[son]);
 86 }
 87 
 88 int lquery_downward(int anc,int son) {
 89     int ans=0,tmp;
 90     while(dep[top[son]]>dep[anc]) {
 91         tmp=query(1,1,n,sid[top[son]],sid[son]);
 92         if(tmp) ans=tmp;
 93         son=fa[top[son]][0];
 94     }
 95     tmp=query(1,1,n,sid[anc],sid[son]);
 96     if(tmp) ans=tmp;
 97     return ans;
 98 }
 99 
100 int tquery(int p,int q){
101     int l=lca(p,q),tmp;
102     tmp=lquery_upward(l,p);
103     if(tmp) return tmp;
104     else return lquery_downward(l,q);
105 }
106 
107 int main(){
108     ios::sync_with_stdio(false);
109     cin>>n>>m;
110     for(int i=1;i<n;i++) cin>>t1>>t2, g[t1].push_back(t2), g[t2].push_back(t1);
111     dep[1]=1; dfs1(1);
112     memset(vis,0,sizeof vis);
113     dfs2(1);
114     lca_presolve();
115     
116     for(int i=1;i<=m;i++) {
117         cin>>t1>>t2;
118         if(t1==0) tmodify(t2);
119         else t3=tid[tquery(1,t2)], cout<<(t3==0?-1:t3)<<endl;    
120     }
121 }