题意是给定一棵树,然后一种操作是指定一个点,这个点及这个点的的子树被染色,另一种操作是指定一个点,问这个点的颜色。
用dfs序建线段树。思路相当于,把当前节点管理所有儿子节点,转换为当前节点对应一条包含所有儿子的线段,
如何转换呢?dfs的时候,访问到当前节点x后,给节点x一个在线段树中的下标cnt,即节点x在线段树中对应的起点,记录为L[x] =cnt,继续深入,重复之前的操作,cnt不断加1。dfs再次返回到x时,我们知道节点x所管理的儿子在线段树中的终点为cnt,记录为R[x] = cnt,那么x节点对应的线段在线段树中为[L[x], R[x]],这样就完成了树到线段树的映射。
之后就是对应的区间懒惰更新,单点查询。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 2e5+10;
vector<int> edge[maxn];
int pre[maxn],L[maxn],R[maxn],tree[maxn],lazy[maxn],cnt;
void Dfs(int p)
{
L[p] = ++cnt;
for(int i = 0;i < edge[p].size(); i++)
Dfs(edge[p][i]);
R[p] = cnt;
}
void Push(int p)
{
if(lazy[p] != -1)
{
tree[p * 2] = tree[p * 2 + 1] = tree[p];
lazy[p * 2] = lazy[p * 2 + 1] = tree[p];
lazy[p] = -1;
}
}
void Change(int p,int l,int r,int a,int b,int num)
{
if(a <= l && r <= b)
tree[p] = lazy[p] = num;
else
{
Push(p);
int mid = (l + r) / 2;
if(a <= mid)
Change(p * 2,l,mid,a,b,num);
if(b > mid)
Change(p * 2 + 1,mid + 1,r,a,b,num);
}
}
int Query(int p,int l,int r,int x)
{
if(l == r && l == x)
return tree[p];
else
{
int mid = (l + r) / 2;
Push(p);
if(x <= mid)
return Query(p * 2,l,mid,x);
if(x > mid)
return Query(p * 2 + 1,mid + 1,r,x);
}
}
int main()
{
int t,x,y,cas = 0;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d",&n);
cnt = 0;
memset(pre,0,sizeof(pre));
memset(tree,-1,sizeof(pre));
memset(lazy,-1,sizeof(lazy));
for(int i = 1;i <= n; i++)
edge[i].clear();
for(int i = 0;i < n-1; i++)
{
scanf("%d %d",&x,&y);
edge[y].push_back(x);
++pre[x];
}
for(int i = 1;i <= n; i++)
{
if(!pre[i])
{
Dfs(i);
break;
}
}
scanf("%d",&m);
char op[5];
printf("Case #%d:\n",++cas);
for(int i = 0;i < m; i++)
{
scanf("%s",op);
if(op[0] == 'C')
{
scanf("%d",&x);
printf("%d\n",Query(1,1,cnt,L[x]));
}
else if(op[0] == 'T')
{
scanf("%d %d",&x,&y);
Change(1,1,cnt,L[x],R[x],y);
}
}
}
return 0;
}