You are given a tree (an acyclic undirected connected graph) with N
nodes. The tree nodes are numbered from 1 to N. In the start, the
color of any node in the tree is white.
We will ask you to perfrom some instructions of the following form:
0 i : change the color of the i-th node (from white to black, or from black to white); or 1 v : ask for the id of the first black node on the path from node 1 to node v. if it doesn't exist, you may return -1 as its result.
Input
In the first line there are two integers N and Q.
In the next N-1 lines describe the edges in the tree: a line with two
integers a b denotes an edge between a and b.
The next Q lines contain instructions “0 i” or “1 v” (1 ≤ i, v ≤ N).
Output
For each “1 v” operation, write one integer representing its result.
樹鍊剖分,維護路徑上深度最小的黑點。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fir[],ne[],to[],
val[],
dep[],fa[],size[],
son[],pos[],top[],
n,q,clo;
void add(int num,int u,int v)
{
ne[num]=fir[u];
fir[u]=num;
to[num]=v;
}
void dfs1(int u)
{
int v;
size[u]=;
for (int i=fir[u];i;i=ne[i])
if ((v=to[i])!=fa[u])
{
dep[v]=dep[u]+;
fa[v]=u;
dfs1(v);
size[u]+=size[v];
if (!son[u]||size[son[u]]<size[v]) son[u]=v;
}
}
void dfs2(int u)
{
int v;
pos[u]=++clo;
if (son[u])
{
top[son[u]]=top[u];
dfs2(son[u]);
}
for (int i=fir[u];i;i=ne[i])
if ((v=to[i])!=fa[u]&&v!=son[u])
{
top[v]=v;
dfs2(v);
}
}
void build(int p,int L,int R)
{
val[p]=-;
if (L==R) return;
int mid=L+R>>;
if (L<=mid) build(p*2,L,mid);
if (mid<R) build(p*2+,mid+,R);
}
void init()
{
int u,v;
scanf("%d%d",&n,&q);
for (int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
add(i*2,u,v);
add(i*2+,v,u);
}
dep[]=;
dfs1();
top[]=;
dfs2();
build(,,n);
}
void modi(int p,int L,int R,int u)
{
int x,y;
if (L==R)
{
if (val[p]==-) val[p]=u;
else val[p]=-;
return;
}
int mid=L+R>>;
if (pos[u]<=mid) modi(p*2,L,mid,u);
else modi(p*2+,mid+,R,u);
x=L<=mid?val[p*2]:-;
y=mid<R?val[p*2+]:-;
if (x==-||(y>&&dep[y]<dep[x])) val[p]=y;
else val[p]=x;
}
int qry(int p,int L,int R,int l,int r)
{
int x,y;
if (l<=L&&R<=r) return val[p];
int mid=L+R>>;
x=l<=mid?qry(p*2,L,mid,l,r):-;
y=r>mid?qry(p*2+,mid+,R,l,r):-;
if (x==-||(y>&&dep[y]<dep[x])) return y;
return x;
}
int query(int u)
{
int ans=-,x;
while (top[u]!=)
{
x=qry(,,n,pos[top[u]],pos[u]);
if (x>&&(ans==-||dep[x]<dep[ans])) ans=x;
u=fa[top[u]];
}
x=qry(,,n,,pos[u]);
if (x>&&(ans==-||dep[x]<dep[ans])) ans=x;
return ans;
}
int main()
{
int u,x;
init();
while (q--)
{
scanf("%d%d",&x,&u);
if (x) printf("%d\n",query(u));
else modi(,,n,u);
}
}