题目描述
给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白
有两种操作：
0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）
1 v : 询问1到v的路径上的第一个黑点，若无，输出-1
输入格式
第一行 N，Q，表示N个点和Q个操作
第二行到第N行N-1条无向边
再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).
输出格式
对每个1 v操作输出结果
/* *P4116 QTree3 *线段树维护的是每个区间深度最少的节点 */ #include<bits/stdc++.h> using namespace std; const int maxn=1e5+100; int n,m; vector<int> g[maxn]; int a[maxn]; int son[maxn]; int id[maxn]; int fa[maxn]; int cnt; int dep[maxn]; int size[maxn]; int top[maxn]; int w[maxn]; int wt[maxn]; int father[20][maxn]; struct node { int l,r; int sum=1e9; int lazy; }segTree[maxn*4]; void build (int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; if (l==r) { segTree[i].sum=1e9; return; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum); } void update (int i,int p) { //单点修改 if (segTree[i].l==p&&segTree[i].r==p) { if (a[p]==0) { a[p]=1; segTree[i].sum=wt[p]; return; } else { a[p]=0; segTree[i].sum=1e9; return; } } int mid=(segTree[i].l+segTree[i].r)>>1; if (p<=mid) update(i<<1,p); if (p>mid) update(i<<1|1,p); segTree[i].sum=min(segTree[i<<1].sum,segTree[i<<1|1].sum); } int query (int i,int l,int r) { if (l<=segTree[i].l&&segTree[i].r<=r) return segTree[i].sum; int mid=(segTree[i].l+segTree[i].r)>>1; int ans=1e9; if (l<=mid) ans=min(ans,query(i<<1,l,r)); if (r>mid) ans=min(ans,query(i<<1|1,l,r)); return ans; } int qRange (int x,int y) { int ans=1e9; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); ans=min(ans,query(1,id[top[x]],id[x])); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); ans=min(ans,query(1,id[x],id[y])); return ans; } void dfs1 (int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; father[0][x]=f; for (int y:g[x]) { if (y==f) continue; dfs1(y,x,deep+1); size[x]+=size[y]; if (size[y]>maxson) son[x]=y,maxson=size[y]; } } void dfs2 (int x,int topf) { id[x]=++cnt; wt[cnt]=dep[x]; top[x]=topf; if (!son[x]) return; dfs2(son[x],topf); for (int y:g[x]) { if (y==fa[x]||y==son[x]) continue; dfs2(y,y); } } int main () { scanf("%d%d",&n,&m); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs1(1,0,1); dfs2(1,1); build(1,1,n); for (int i=1;i<=17;i++) for (int j=1;j<=n;j++) father[i][j]=father[i-1][father[i-1][j]]; while (m--) { int op; scanf("%d",&op); if (op==0) { int x; scanf("%d",&x); update(1,id[x]); } else { int x; scanf("%d",&x); int ans=qRange(1,x); if (ans==1e9) { printf("-1 "); continue; } for (int i=17;i>=0;i--) if (dep[x]-ans>>i) x=father[i][x]; printf("%d ",x); } } }