解题：洛谷 p2633 Count on a tree

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=100005,K=18;
 6 int p[N],noww[2*N],goal[2*N];
 7 int siz[N],anc[N],dep[N],imp[N],top[N];
 8 int num[N],tep[N],cmt[N*K],son[N*K][2],sum[N*K],uni[N*K];
 9 int n,m,t1,t2,t3,lca,cnt,tot,len,xnt,ans,n1,n2,n3,n4;
10 void link(int f,int t)
11 {
12     noww[++cnt]=p[f];
13     goal[cnt]=t,p[f]=cnt;
14 }
15 int Create(int pre,int l,int r,int pos)
16 {
17     int nde=++xnt;
18     son[nde][0]=son[pre][0];
19     son[nde][1]=son[pre][1];
20     sum[nde]=sum[pre]+1;
21     if(l<r)
22     {
23         int mid=(l+r)/2;
24         if(pos<=mid) son[nde][0]=Create(son[pre][0],l,mid,pos);
25         else son[nde][1]=Create(son[pre][1],mid+1,r,pos);
26     }
27     return nde;
28 }
29 int Query(int l,int r,int rnk)
30 {
31     if(l==r) return l;
32     int mid=(l+r)/2,noww=sum[son[n1][0]];
33     noww+=sum[son[n2][0]]-sum[son[n3][0]]-sum[son[n4][0]];
34     if(rnk<=noww)
35     {
36         n1=son[n1][0],n2=son[n2][0],n3=son[n3][0],n4=son[n4][0];
37         return Query(l,mid,rnk);
38     }
39     else
40     {
41         n1=son[n1][1],n2=son[n2][1],n3=son[n3][1],n4=son[n4][1];
42         return Query(mid+1,r,rnk-noww);
43     }
44 }
45 void DFS(int nde,int fth,int dth)
46 {
47     int tmp=0;
48     siz[nde]=1,dep[nde]=dth,anc[nde]=fth;
49     cmt[nde]=Create(cmt[anc[nde]],1,len,num[nde]);
50     for(int i=p[nde];i;i=noww[i])
51         if(goal[i]!=fth)
52         {
53             DFS(goal[i],nde,dth+1);
54             siz[nde]+=siz[goal[i]];
55             if(siz[goal[i]]>tmp)
56                 tmp=siz[goal[i]],imp[nde]=goal[i];
57         }
58 }
59 void MARK(int nde,int tpp)
60 {
61     top[nde]=tpp;
62     if(imp[nde])
63     {
64         MARK(imp[nde],tpp);
65         for(int i=p[nde];i;i=noww[i])
66             if(goal[i]!=anc[nde]&&goal[i]!=imp[nde])
67                 MARK(goal[i],goal[i]);
68     }
69 }
70 int LCA(int x,int y)
71 {
72     while(top[x]!=top[y])
73     {
74         if(dep[top[x]]<dep[top[y]]) 
75             swap(x,y); x=anc[top[x]];
76     }
77     return dep[x]<dep[y]?x:y;
78 }
79 int main ()
80 {
81     scanf("%d%d",&n,&m);
82     for(int i=1;i<=n;i++)
83         scanf("%d",&num[i]),tep[i]=num[i];
84     sort(tep+1,tep+1+n),len=unique(tep+1,tep+1+n)-tep-1;
85     for(int i=1;i<=n;i++) 
86         num[i]=lower_bound(tep+1,tep+1+len,num[i])-tep;
87     for(int i=1;i<n;i++)
88         scanf("%d%d",&t1,&t2),link(t1,t2),link(t2,t1);
89     DFS(1,0,1); MARK(1,1);
90     for(int i=1;i<=m;i++)
91     {
92         scanf("%d%d%d",&t1,&t2,&t3),t1^=ans,lca=LCA(t1,t2);
93         n1=cmt[t1],n2=cmt[t2],n3=cmt[lca],n4=cmt[anc[lca]];
94         printf("%d\n",ans=tep[Query(1,len,t3)]);
95     }
96     return 0;
97 }