Description
给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白
有两种操作：
0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）
1 v : 询问1到v的路径上的第一个黑点，若无，输出-1
Input
第一行 N，Q，表示N个点和Q个操作
第二行到第N行N-1条无向边
再之后Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).
Output
对每个1 v操作输出结果
很明显.树上区间问题,我们考虑树链剖分.
单点修改,我们就直接修改即可.
而对于这个询问操作,则有一些思维难度.(不是很难的
首先,遇到一个线段树上的节点.我们需要考虑其是否有黑点,如果有的话,我们优先选择左子树中的黑点,(可以保证是从(1)到(v)的第一个黑点)
具体实现起来不难,注意数组要开够.
复杂度(O(能过))
代码
#include<cstdio>
#include<cctype>
#include<cstring>
#define R register
#define N 200008
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int n,m,head[N],tot;
struct cod{int u,v;}edge[N<<2];
inline void add(int x,int y)
{
edge[++tot].u=head[x];
edge[tot].v=y;
head[x]=tot;
}
int f[N],depth[N],size[N],son[N];
void dfs1(int u,int fa)
{
f[u]=fa;depth[u]=depth[fa]+1;size[u]=1;
for(R int i=head[u];i;i=edge[i].u)
{
if(edge[i].v==fa)continue;
dfs1(edge[i].v,u);
size[u]+=size[edge[i].v];
if(son[u]==-1 or size[son[u]]<size[edge[i].v])
son[u]=edge[i].v;
}
}
int idx,dfn[N],fdfn[N],top[N];
void dfs2(int u,int t)
{
dfn[u]=++idx;fdfn[idx]=u;top[u]=t;
if(son[u]==-1)return;
dfs2(son[u],t);
for(R int i=head[u];i;i=edge[i].u)
{
if(dfn[edge[i].v])continue;
dfs2(edge[i].v,edge[i].v);
}
}
bool tr[N<<2];
int pos[N<<2];
#define ls o<<1
#define rs o<<1|1
inline void up(int o)
{
tr[o]=tr[ls] | tr[rs];
pos[o]= tr[ls] ? pos[ls]:(tr[rs]? pos[rs]:-1);
}
void change(int o,int l,int r,int poss)
{
if(l==r){tr[o]^=1;pos[o]=tr[o] ? fdfn[l]:-1; return;}
int mid=(l+r)>>1;
if(poss<=mid)change(ls,l,mid,poss);
else change(rs,mid+1,r,poss);
up(o);
}
int query(int o,int l,int r,int x,int y)
{
if(l>y or r<x)return -1;
if(x<=l and y>=r)return pos[o];
int mid=(l+r)>>1,le,ri;
le=query(ls,l,mid,x,y),ri=query(rs,mid+1,r,x,y);
return le==-1 ? ri:le;
}
inline int tquery(int x)
{
int ans=-1,p,fx=top[x];
while(fx!=1)
{
p=query(1,1,n,dfn[fx],dfn[x]);
ans=(p==-1? ans:p);
x=f[fx];fx=top[x];
}
p=query(1,1,n,1,dfn[x]);
ans=(p==-1 ? ans : p);
return ans;
}
int main()
{
in(n),in(m);
memset(son,-1,sizeof son);
memset(pos,-1,sizeof pos);
for(R int i=1,x,y;i<n;i++)
{
in(x),in(y);
add(x,y);add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(R int opt,x;m;m--)
{
in(opt);in(x);
if(opt==0)
change(1,1,n,dfn[x]);
else printf("%d
",tquery(x));
}
}