A1505. 树（张闻涛）
试题来源
2013中国国家集训队第二次作业
问题描述
给定一棵N个节点的树，每个点有一个权值，有M个询问(a,b,c)若a 为1，回答b到c路径上的最小权值，若a为2，回答b到c路径上的最大权值，若a为3，回答b到c路径上的所有权值的中位数，k个数的中位数定义为从0到k-1编号从小到大排序后k/2号的那个数。
输入格式
第一行两个整数N，M
第二行N个整数，v[1]~v[n]，代表每个节点的权值。
接下来N-1行每行两个整数x，y代表x和y有一条边
最后M行每行三个整数a，b，c，表示一组询问。
第二行N个整数，v[1]~v[n]，代表每个节点的权值。
接下来N-1行每行两个整数x，y代表x和y有一条边
最后M行每行三个整数a，b，c，表示一组询问。
输出格式
共M行，每行一个整数，代表询问的答案。
样例输入
5 3
1 3 2 4 5
1 2
2 4
4 3
4 5
1 1 5
2 1 3
3 1 5
1 3 2 4 5
1 2
2 4
4 3
4 5
1 1 5
2 1 3
3 1 5
样例输出
1
4
4
4
4
数据规模和约定
共20个数据
数据1~3 N,M<=1000
数据4~6 N,M<=5000
数据7~10 N,M<=10000
数据11~18 N,M<=30000
数据19~20 N,M<=100000
数据1~3 N,M<=1000
数据4~6 N,M<=5000
数据7~10 N,M<=10000
数据11~18 N,M<=30000
数据19~20 N,M<=100000
题解：
倍增LCA+可持久化线段树+DFS序
直接把可持久化线段树建到DFS序上即可。
每个点由其 父亲结点 为基础建立即可。
设询问 u -> v 路径，路径上点数为k个。
然后若a=1，输出链上排第一小的。
a=2，输出链上排第k小的。
a=3，输出链上排第k/2+1小的。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
struct node
{
int begin,end,next;
}edge[MAXN*];
struct NODE
{
int left,right;
}tree[MAXN*];
int cnt,Head[MAXN],SIZE,deep[MAXN],P[MAXN][],tot,root[MAXN],n,sum[MAXN*],val[MAXN],cc[MAXN],pos[MAXN],value[MAXN];
bool vis[MAXN];
void addedge(int bb,int ee)
{
edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee)
{
addedge(bb,ee);addedge(ee,bb);
}
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void dfs(int u)
{
int i,v;
vis[u]=true;
SIZE++;pos[u]=SIZE;value[SIZE]=u;
for(i=Head[u];i!=-;i=edge[i].next)
{
v=edge[i].end;
if(vis[v]==false)
{
deep[v]=deep[u]+;
P[v][]=u;
dfs(v);
}
}
}
void Ycl()
{
int i,j;
for(j=;(<<j)<=n;j++)
{
for(i=;i<=n;i++)
{
if(P[i][j-]!=-)P[i][j]=P[P[i][j-]][j-];
}
}
}
int LCA(int x,int y)
{
if(deep[x]<deep[y])swap(x,y);
int i,j;
for(i=;(<<i)<=deep[x];i++);i--;
for(j=i;j>=;j--)if(deep[x]-(<<j)>=deep[y])x=P[x][j];
if(x==y)return x;
for(j=i;j>=;j--)
{
if(P[x][j]!=-&&P[x][j]!=P[y][j])
{
x=P[x][j];
y=P[y][j];
}
}
return P[x][];
}
void Build(int x,int &y,int l,int r,int B)
{
y=++SIZE;
sum[y]=sum[x]+;
if(l==r)return;
tree[y].left=tree[x].left;tree[y].right=tree[x].right;
int mid=(l+r)/;
if(B<=mid)Build(tree[x].left,tree[y].left,l,mid,B);
else Build(tree[x].right,tree[y].right,mid+,r,B);
}
int Query(int l,int r,int A,int B,int C,int D,int Q)
{
if(l==r)return l;
int mid,delta=sum[tree[A].left]+sum[tree[B].left]-sum[tree[C].left]-sum[tree[D].left];
mid=(l+r)/;
if(Q<=delta)return Query(l,mid,tree[A].left,tree[B].left,tree[C].left,tree[D].left,Q);
else return Query(mid+,r,tree[A].right,tree[B].right,tree[C].right,tree[D].right,Q-delta);
}
int query(int u,int v,int lca,int k)
{
int A=pos[u],B=pos[v],C=pos[lca],D=pos[P[lca][]];
return Query(,tot,root[A],root[B],root[C],root[D],k);
}
int main()
{
int m,i,wz,s1,s2,s3,lca,k,bb,ee;
n=read();m=read();
for(i=;i<=n;i++)val[i]=read(),cc[i]=val[i];
sort(cc+,cc+n+);
tot=unique(cc+,cc+n+)-(cc+);
memset(Head,-,sizeof(Head));cnt=;
for(i=;i<n;i++){bb=read();ee=read();addedge1(bb,ee);}
memset(P,-,sizeof(P));
SIZE=;
dfs();Ycl();
SIZE=;
for(i=;i<=n;i++)//按树上顺序插入.
{
k=value[i];
wz=lower_bound(cc+,cc+tot+,val[k])-cc;
Build(root[pos[P[k][]]],root[i],,tot,wz);
}
SIZE=;
for(i=;i<=m;i++)
{
s1=read();s2=read();s3=read();
if(s1==){lca=LCA(s2,s3);printf("%d\n",cc[query(s2,s3,lca,)]);}
else if(s1==){lca=LCA(s2,s3);k=deep[s2]+deep[s3]-*deep[lca]+;printf("%d\n",cc[query(s2,s3,lca,k)]);}
else {lca=LCA(s2,s3);k=(deep[s2]+deep[s3]-*deep[lca]+)/;printf("%d\n",cc[query(s2,s3,lca,k)]);}
}
fclose(stdin);
fclose(stdout);
return ;
}