Water Tree CodeForces 343D 树链剖分+线段树
题意
给定一棵n个n-1条边的树，起初所有节点权值为0。
然后m个操作， 1 x:把x为根的子树的点的权值修改为1； 2 x：把x结点到根路径上的点修改为0； 3 x：查询结点x的值。
解题思路
这个因为是在树上进行的操作，所以首先需要把树进行一些转化，比如使用dfs序列转变成一维的，这样方便使用线段树或则树状数组来进行操作。但是因为这里的操作2需要把x节点和它的父节点赋值为0，所以需要树链剖分来进行处理。
关于树链剖分的讲解可以参照我的代码，如果是初学者的话，我有一篇博文专门总结了一些优秀的关于树链剖分的文章，可以参考，点我进去
代码实现
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=5e5+7;
struct node{
int l, r;
int val, lazy; //val表示在l到r的范围内是不是都有水，lazy就是标记了
}t[maxn<<2]; //线段树的基本单元
struct edge{
int to, next;
}e[maxn<<1]; //采用链式向前星的形式来存边
int son[maxn], size[maxn], f[maxn], dep[maxn];
int in[maxn], top[maxn], cnt;
int head[maxn], len;
int n, m;
void init()
{
len=cnt=0;
for(int i=1; i<=n; i++)
head[i]=-1;
}
void add(int u, int v)
{
e[len].to=v;
e[len].next=head[u];
head[u]=len++;
}
void dfs1(int u, int fa, int depth) //这个dfs主要解决每个点的基本信息，如深度，父节点是谁，点的规模大小和它的重儿子
{
f[u]=fa;
dep[u]=depth;
size[u]=1; //点的规模包括自己和自己的所有子儿子。
for(int i=head[u]; i!=-1; i=e[i].next)
{
int v=e[i].to;
if(v==fa) //因为是无向树，所以要注意不能回去
continue;
dfs1(v, u, depth+1);
size[u]+=size[v];
if(size[v] > size[son[u]]) //一个点只有一个重儿子，就是规模最大的子儿子
son[u]=v; //记录u这个点的重儿子
}
}
void dfs2(int u, int t) //这里是dfs序，但是有所不同，在处理一个节点的子儿子时，先处理它的重儿子，也就是先处理重链。
{
top[u]=t; //链的顶部
in[u]=++cnt;//这里存储树按照新的排列方式的顺序，从1到n
if(!son[u]) //如果没有重儿子说明到了叶子节点
return ;
dfs2(son[u], t);//先处理重儿子
for(int i=head[u]; i!=-1; i=e[i].next) //下面是处理u的轻儿子
{
int v=e[i].to;
if(v==son[u] || v==f[u]) //如果遇到重儿子和它的父节点就不能再处理一遍了。
continue;
dfs2(v, v); //轻儿子的顶点就是本身
}
}
//-----------------------------这里是线段树----------------------------------
void up(int rt)
{
t[rt].val=(t[rt<<1].val && t[rt<<1|1].val);
}
void build(int rt, int l, int r)
{
t[rt].l=l;
t[rt].r=r;
t[rt].lazy=-1;
t[rt].val=0;
if(l==r)
return ;
int mid=(l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
void down(int rt)
{
if(t[rt].lazy==-1) return ;
int l=rt<<1, r=rt<<1|1;
t[l].val=t[l].lazy=t[rt].lazy;
t[r].val=t[r].lazy=t[rt].lazy;
t[rt].lazy=-1;
}
void update(int rt, int l, int r, int v)
{
if(l<=t[rt].l && t[rt].r<=r)
{
t[rt].lazy=t[rt].val=v;
return ;
}
down(rt);
int mid=(t[rt].l+t[rt].r)>>1;
if(l<=mid)
update(rt<<1, l, r, v);
if(r>mid)
update(rt<<1|1, l, r, v);
up(rt);
}
int query(int rt, int x)
{
if(t[rt].l==t[rt].r)
return t[rt].val;
down(rt);
int mid=(t[rt].l+t[rt].r)>>1;
if(x<=mid) return query(rt<<1, x);
else return query(rt<<1|1, x);
}
//--------------------线段树到此结束------------------------------------
void solve(int x) //这里是关键的一步，用来处理一个点和它的祖先们。
{
int f1=top[x]; //在这里，上面使用的top来记录一个重链的上端点的用处就体现出来了。实际上就是用来加速的
while(f1!=1)
{
update(1, in[f1], in[x], 0);
x=f[x];
f1=top[x];
}
update(1, 1, in[x], 0); //不要忘记这一步。
}
int main()
{
scanf("%d", &n);
init();
int x, y;
for(int i=1; i<n; i++)
{
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs1(1, 0, 1);
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &m);
int op;
for(int i=1; i<=m; i++)
{
scanf("%d%d", &op, &x);
if(op==1)
update(1, in[x], in[x]+size[x]-1, 1);
else if(op==2)
solve(x);
else printf("%d\n", query(1, in[x]));
}
return 0;
}