在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作： 标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。） 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先） 你能帮帮他吗?
输入第一行两个正整数N和Q分别表示节点个数和操作次数 接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边 接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。
输出一个正整数，表示结果
5 5 1 2 1 3 2 4 2 5 Q 2 C 2 Q 2 Q 5 Q 3
1 2 2 1
30%的数据，1 ≤ N, Q ≤ 1000 70%的数据，1 ≤ N, Q ≤ 10000 100%的数据，1 ≤ N, Q ≤ 100000
这道题的做法其实挺多的……先说我自己的吧 先dfs一遍，记录dfs序 用线段树维护到结点最近的已标记祖先编号 每次标记操作，就更新它的子节点的最近已标记祖先编号（用lazy） 查询某个点就从根节点往下走，不断pushdown，更新下面结点的最近已标记祖先，一直走到要查询的那个点。 复杂度O(QlogN)
还有一种不错的做法。 把所有操作读入，要标记的节点先都标记上 dfs一遍。记录每个节点的它最近的已标记祖先（包括自己），并查集并在一起 从后往前处理每个操作。 若是标记操作，便把这个标记去掉，将它与父节点并在一起，表明它与它父节点的最近已标记祖先是同一个点。 若是查询操作，这个点的最近已标记祖先便为它所在并查集的根。 这个做法应该比线段树快，但不太好想到。
（线段树版）
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 100005; struct node{ int v; node *next; }pool[N],*h[N]; int cnt; void addedge(int u,int v){ node *p=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p; } int dep[N],dfn[N],out[N]; int tot; void dfs(int u){ int v; dfn[u]=++tot; for(node *p=h[u];p;p=p->next) if(!dep[v=p->v]){ dep[v]=dep[u]+1; dfs(v); } out[u]=tot; } struct tree{ tree *ch[2]; int v; }pool2[N*20],*root; int cnt2; void pushdown(tree *p){ if(dep[p->v]>dep[p->ch[0]->v]) p->ch[0]->v=p->v; if(dep[p->v]>dep[p->ch[1]->v]) p->ch[1]->v=p->v; } void build(tree *p,int l,int r){ p->v=1; if(l==r) return; int mid=(l+r)>>1; build(p->ch[0]=&pool2[++cnt2],l,mid); build(p->ch[1]=&pool2[++cnt2],mid+1,r); } void change(tree *p,int l,int r,int L,int R,int c){ if(dep[c]<dep[p->v]) return; if(l==L && r==R){ if(dep[c]>dep[p->v]) p->v=c; return; } pushdown(p); int mid=(l+r)>>1; if(mid>=R) change(p->ch[0],l,mid,L,R,c); else if(mid<L) change(p->ch[1],mid+1,r,L,R,c); else { change(p->ch[0],l,mid,L,mid,c); change(p->ch[1],mid+1,r,mid+1,R,c); } } int query(tree *p,int l,int r,int L){ if(l==L && r==L) return p->v; pushdown(p); int mid=(l+r)>>1; if(mid>=L) return query(p->ch[0],l,mid,L); return query(p->ch[1],mid+1,r,L); } int n,q; int main() { char ch; int u,v; scanf("%d%d",&n,&q); for(int i=1;i<n;i++) scanf("%d%d",&u,&v),addedge(u,v); dep[1]=1; dfs(1); root=&pool2[++cnt2]; build(root,1,n); for(int i=0;i<q;i++){ ch=getchar(); while(ch!='C' && ch!='Q') ch=getchar(); scanf("%d",&u); if(ch=='C') change(root,1,n,dfn[u],out[u],u); else printf("%d\n",query(root,1,n,dfn[u])); } return 0; }转载于:https://www.cnblogs.com/lindalee/p/8393513.html
相关资源：数据结构—成绩单生成器