题目链接

题目翻译(摘自洛谷)

疯狂科学家Mike培养了一颗有根树,由n个节点组成。每个节点是一个要么装满水要么为空的贮水容器. 树的节点用1~n编号,其中根节点为1.对于每个节点的容器,其子节点的容器均在这一容器下方,并且每个节点都由一根可以向下流水的管道与其子节点连接. Mike想要对这棵树做以下操作:
1将节点v注满水. 这样v和其子节点都会充满水.
2将节点v置空. 这样v及其祖先节点(从v到根节点的路径)都会被置空.
3查询当前节点v是否充满水.
初始时,所有节点都为空. Mike已经制定好了他的操作顺序. 在对树进行实验前,他决定先模拟一下操作. 请你帮助Mike得出他操作后的结果.

思路

裸树链剖分,区间修改,单点查询。

 #include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n,cnt,dcnt,hd[N];
struct edge
{
int to,nxt;
}v[*N];
struct node
{
int fa,son,sz,dep,tp,s,e;
}tr[N];
struct segtree
{
int l,r,stat,tag;
}st[*N];
void addedge(int x,int y)
{
v[++cnt].to=y;
v[cnt].nxt=hd[x];
hd[x]=cnt;
}
void dfs1(int u)
{
tr[u].sz=;
for(int i=hd[u];i;i=v[i].nxt)
if(v[i].to!=tr[u].fa)
{
tr[v[i].to].fa=u;
tr[v[i].to].dep=tr[u].dep+;
dfs1(v[i].to);
tr[u].sz+=tr[v[i].to].sz;
if(tr[v[i].to].sz>tr[tr[u].son].sz)
tr[u].son=v[i].to;
}
}
void dfs2(int u,int top)
{
tr[u].tp=top;
tr[u].s=++dcnt;
if(tr[u].son)
{
dfs2(tr[u].son,top);
for(int i=hd[u];i;i=v[i].nxt)
if(v[i].to!=tr[u].fa&&v[i].to!=tr[u].son)
dfs2(v[i].to,v[i].to);
}
tr[u].e=dcnt;
}
void build(int num,int l,int r)
{
st[num].l=l,st[num].r=r;
st[num].tag=-;
if(l==r)
return ;
int mid=(l+r)/;
build(*num,l,mid),build(*num+,mid+,r);
}
void pushdown(int num)
{
if(st[num].tag!=-)
{
if(st[num].l!=st[num].r)
{
st[*num].stat=st[*num+].stat=st[num].tag;
st[*num].tag=st[*num+].tag=st[num].tag;
}
st[num].tag=-;
}
}
void change(int num,int l,int r,int z)
{
if(l>st[num].r||r<st[num].l)
return ;
if(st[num].l>=l&&st[num].r<=r)
{
st[num].tag=st[num].stat=z;
return ;
}
pushdown(num);
change(*num,l,r,z),change(*num+,l,r,z);
}
int query(int num,int x)
{
if(st[num].l>x||st[num].r<x)
return ;
if(st[num].l==st[num].r)
return st[num].stat;
pushdown(num);
return query(*num,x)+query(*num+,x);
}
void fnd(int x)
{
int f1=tr[x].tp;
while(f1!=)
{
change(,tr[f1].s,tr[x].s,);
x=tr[f1].fa,f1=tr[x].tp;
}
change(,,tr[x].s,);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n-;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y),addedge(y,x);
}
dfs1();
dfs2(,);
build(,,n);
int q,x,y;
scanf("%d",&q);
while(q--)
{
scanf("%d%d",&x,&y);
switch(x)
{
case :
change(,tr[y].s,tr[y].e,);
break;
case :
fnd(y);
break;
case :
printf("%d\n",query(,tr[y].s));
break;
}
}
return ;
}
05-11 13:18