★★ 输入文件：B_Tree.in 输出文件：B_Tree.out 简单对比
时间限制：2 s 内存限制：512 MB
【题目描述】
给定一棵有根树，树根为1，一开始这棵树所有节点均为白色
之后给定一个染色序列，第i个数ai表示将ai这个点染黑
之后给定若干询问
询问第L到第R个染黑的黑点和u所有的LCA中深度最大的LCA的编号
【输入格式】
第一行n，m，q 表示节点总数，染色序列长度，询问个数
以下n-1行，每行u，v描述一条边的两个端点
之后m个正整数表示染色序列
之后q行，每行L，R，u 如题目所示
n，m，q<=200000 可能会有点重复被染色
【输出格式】
对于每个询问输出对应的答案
【样例输入】
5 5 5 1 2 2 3 3 4 1 5 3 2 4 3 2 3 5 4 1 2 1 1 1 2 5 5 2 2 2 4
【样例输出】
4 1 2 2 2
主席树+LCA
屠龙宝刀点击就送
#include <cstdio> #include <vector> #define N 200500 using std::vector; vector<int>edge[N]; struct cmt { int l,r,Size; }tr[N*30]; int k,tot,tim,n,m,q,root[N],siz[N],dad[N][25],dfn[N],pos[N],dep[N]; void dfs(int x) { dfn[x]=++tim; pos[tim]=x; dep[x]=dep[dad[x][0]]+1; for(int i=0;dad[x][i];i++) dad[x][i+1]=dad[dad[x][i]][i]; for(int i=0;i<edge[x].size();++i) { int v=edge[x][i]; if(dad[x][0]!=v) { dad[v][0]=x; dfs(v); } } } void update(int l,int r,int x,int &y,int t) { y=++tot; tr[y].Size=tr[x].Size+1; if(l==r) return; tr[y].l=tr[x].l; tr[y].r=tr[x].r; int mid=(l+r)>>1; if(t<=mid) update(l,mid,tr[x].l,tr[y].l,t); else update(mid+1,r,tr[x].r,tr[y].r,t); } int ask(int l,int r,int lx,int rx) { if(l==r) return l; int mid=(l+r)>>1; if(k<=tr[tr[rx].l].Size-tr[tr[lx].l].Size) return ask(l,mid,tr[lx].l,tr[rx].l); else {k-=tr[tr[rx].l].Size-tr[tr[lx].l].Size;return ask(mid+1,r,tr[lx].r,tr[rx].r);} } int query(int l,int r,int x,int y,int a,int b) { if(l==a&&r==b) return tr[y].Size-tr[x].Size; int mid=(l+r)>>1; if(a>mid) return query(mid+1,r,tr[x].r,tr[y].r,a,b); else if(b<=mid) return query(l,mid,tr[x].l,tr[y].l,a,b); else return query(l,mid,tr[x].l,tr[y].l,a,mid)+query(mid+1,r,tr[x].r,tr[y].r,mid+1,b); } inline void swap(int &m,int &n) { int tmp=n; n=m; m=tmp; } inline int lca(int x,int y) { if(dep[x]>dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[dad[y][i]]>=dep[x]) y=dad[y][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(dad[x][i]!=dad[y][i]) x=dad[x][i],y=dad[y][i]; return dad[x][0]; } int main() { scanf("%d%d%d",&n,&m,&q); for(int u,v,i=1;i<n;++i) { scanf("%d%d",&u,&v); edge[u].push_back(v); edge[v].push_back(u); } dfs(1); for(int a,i=1;i<=m;++i) { scanf("%d",&a); update(1,n,root[i-1],root[i],dfn[a]); } for(int l,r,u;q--;) { scanf("%d%d%d",&l,&r,&u); if(dfn[u]==1) { k=1; printf("%d ",lca(u,pos[ask(1,n,root[l-1],root[r])])); } else if(dfn[u]==n) { k=r-l+1; printf("%d ",lca(u,pos[ask(1,n,root[l-1],root[r])])); } else { int tmp=query(1,n,root[l-1],root[r],1,dfn[u]-1); if(tmp) { k=tmp; int x=pos[ask(1,n,root[l-1],root[r])]; if(tmp==r-l+1) printf("%d ",lca(u,x)); else { k=tmp+1; int y=pos[ask(1,n,root[l-1],root[r])]; x=lca(x,u); y=lca(y,u); printf("%d ",dep[x]>dep[y]?x:y); } } else k=1,printf("%d ",lca(u,pos[ask(1,n,root[l-1],root[r])])); } } return 0; }