题意：
有一棵树，每次两种操作，给一个点打上标记或者询问一个点最近的一个打了标记的祖先（包括自己），一开始只有根节点有标记
题解：
本题方法较多，这里采用一种最简单的做法。
先将树转化成dfs序，每一次打标记操作相当于在自己的子树上覆盖一个值，这个值也就是自己的深度。但本题要求取最近的，也就是深度最大的，所以在线段树覆盖中取一个max即可，另外要记录下深度最大的节点来作为询问操作的答案。
然后就是简单的线段树覆盖+标记操作。
#include<cstdio> #include<vector> #include<algorithm> #include<cstdlib> using namespace std; int n,m,dep[100002],dfn[100002],zjds[100002],df; vector<int>g[100002]; typedef struct{ int maxd,maxn,fd,fn; }P; P p[400002]; void dfs(int x,int y){ dep[x]=dep[y]+1;dfn[x]=++df;zjds[x]=1; for (int i=0;i<g[x].size();i++) if (g[x][i]!=y) { dfs(g[x][i],x);zjds[x]+=zjds[g[x][i]]; } } void pushdown(int root){ if (p[root].fd) { if (p[root].fd>p[root*2].maxd) { p[root*2].maxd=p[root].fd;p[root*2].maxn=p[root].fn; } if (p[root].fd>p[root*2].fd) { p[root*2].fd=p[root].fd;p[root*2].fn=p[root].fn; } if (p[root].fd>p[root*2+1].maxd) { p[root*2+1].maxd=p[root].fd;p[root*2+1].maxn=p[root].fn; } if (p[root].fd>p[root*2+1].fd) { p[root*2+1].fd=p[root].fd;p[root*2+1].fn=p[root].fn; } p[root].fd=p[root].fn=0; } } void gengxin(int root,int begin,int end,int begin2,int end2,int deep,int num){ if (begin>end2 || end<begin2)return; if (begin>=begin2 && end<=end2) { if (deep>p[root].maxd) { p[root].maxd=deep;p[root].maxn=num; } if (deep>p[root].fd) { p[root].fd=deep;p[root].fn=num; } return; } int mid=(begin+end)/2;pushdown(root); gengxin(root*2,begin,mid,begin2,end2,deep,num);gengxin(root*2+1,mid+1,end,begin2,end2,deep,num); } int chaxun(int root,int begin,int end,int wz){ if (begin==end)return p[root].maxn; int mid=(begin+end)/2;pushdown(root); if (wz<=mid)return chaxun(root*2,begin,mid,wz); else return chaxun(root*2+1,mid+1,end,wz); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); g[u].push_back(v);g[v].push_back(u); } dfs(1,0);gengxin(1,1,n,1,n,dep[1],1); for (int i=1;i<=m;i++) { char ch[5];int a; scanf("%s%d",ch+1,&a); if (ch[1]=='C')gengxin(1,1,n,dfn[a],dfn[a]+zjds[a]-1,dep[a],a); else printf("%d ",chaxun(1,1,n,dfn[a])); } return 0; }