題目描述:
給出N個點的一棵樹(N-1條邊),節點有白有黑,初始全為白
有兩種操作:
0 i : 改變某點的顔色(原來是黑的變白,原來是白的變黑)
1 v : 詢問1到v的路徑上的第一個黑點,若無,輸出-1
解析:
樹鍊剖分+線段樹。
代碼:
#include <bits/stdc++.h>
using namespace std;
const int Max=100005;
int n,m,s,tot,ans;
int first[Max],size[Max],son[Max],dep[Max],fa[Max];
int rev[Max],seg[Max],tree[Max<<2],top[Max];
struct shu{int to,next;};
shu edge[Max<<1];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void print(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline void build(int x,int y)
{
edge[++s].next=first[x];
first[x]=s;
edge[s].to=y;
}
inline void dfs1(int p)
{
size[p]=1;
for(int u=first[p];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa[p]) continue;
fa[to]=p,dep[to]=dep[p]+1,dfs1(to),size[p]+=size[to];
if(size[to]>size[son[p]]) son[p]=to;
}
}
inline void dfs2(int p,int tp)
{
top[p]=tp,seg[rev[p]=++tot]=p;
if(!son[p]) return;
dfs2(son[p],tp);
for(int u=first[p];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==son[p]||to==fa[p]) continue;
dfs2(to,to);
}
}
inline void update(int root){tree[root]=tree[root<<1]+tree[root<<1|1];}
inline void change(int root,int l,int r,int pos)
{
if(l==r&&l==pos){tree[root]^=1;return;}
int mid=(l+r)>>1;
if(pos<=mid) change(root<<1,l,mid,pos);
else change(root<<1|1,mid+1,r,pos);
update(root);
}
inline int find(int root,int l,int r)
{
if(l==r) return tree[root]?seg[l]:-1;
int mid=(l+r)>>1;
if(tree[root<<1]) return find(root<<1,l,mid);
else if(tree[root<<1|1]) return find(root<<1|1,mid+1,r);
else return -1;
}
inline int Q(int root,int l,int r,int L,int R)
{
if(L<=l&&R>=r) return find(root,l,r);
int mid=(l+r)>>1,ans=-1;
if(L<=mid) ans=Q(root<<1,l,mid,L,R);
if(~ans) return ans;
if(R>mid) ans=Q(root<<1|1,mid+1,r,L,R);
return ans;
}
inline int ask(int p)
{
ans=-1;
while(top[p]!=1)
{
int x=Q(1,1,tot,rev[top[p]],rev[p]);
if(~x) ans=x;
p=fa[top[p]];
}
int x=Q(1,1,tot,rev[1],rev[p]);
if(~x) ans=x;
return ans;
}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<n;i++)
{
int x=get_int(),y=get_int();
build(x,y),build(y,x);
}
dfs1(1),dfs2(1,1);
while(m--)
{
int tag=get_int(),x=get_int();
if(!tag) change(1,1,tot,rev[x]);
else print(ask(x)),putchar('\n');
}
return 0;
}