DLKKILL

DLKKILL's world

Codeforces Round #442 (Div. 2) - Danil and a Part-time Job(DFS序+线段树维护)

题目链接:Danil and a Part-time Job

题目大意:

有一颗树,所有节点的状态可能为1或0.

给出所有节点的初始状态,有两种操作。

  1. 查询某一结点子树(包括该节点)上所有为1的节点数目

  2. 某一结点子树(包括该节点)上所有节点状态反转,1->0,0->1

题目分析:

是一道很明显的线段树维护的DFS序。

首先求出DFS序列,然后建立线段树。

每一次对于树的操作可以转变成对于区间的操作。

补充:

  1. DFS序详解

  2. DFS序总结

给出代码:

#include <iostream> 
#include <queue>  
#include <algorithm> 
#include <string> 
#include <vector>
#include <cstdio>
using namespace std; 
const int maxn=200000+10; 
const int inf=0x3f3f3f3f;
int tree_no;
vector<int> g[maxn];
int l[maxn],r[maxn],rk[maxn];
int t[maxn];
int sum[maxn<<2];
int rev[maxn<<2];
int q;
void dfs(int u,int f)
{
l[u]=++tree_no;
//rk[u]=tree_no;
rk[tree_no]=u;
for(int i=0;i<g[u].size();i++)
{
int t=g[u][i];
if(t==f)
continue;
    dfs(t,u);
}
r[u]=tree_no;
}
void push_node(int x)
{
    sum[x]=sum[x<<1]+sum[x<<1|1];
}
void build(int l,int r,int root)
{
    if(l==r)
{
sum[root]+=t[rk[l]];
return;
}
int mid=l+((r-l)>>1);
build(l,mid,root<<1);
build(mid+1,r,root<<1|1);
push_node(root);
return;
}
void push_down(int root,int len)
{
if(rev[root])
{
sum[root<<1]=(len-(len>>1))-sum[root<<1];
sum[root<<1|1]=(len>>1)-sum[root<<1|1];
rev[root<<1]^=1;
rev[root<<1|1]^=1;
rev[root]=0;
return;
}
return;
}
void change(int l,int r,int L,int R,int root)
{
if(l<=L&&R<=r)
{
int len=R-L+1;
sum[root]=len-root[sum];
rev[root]^=1;
return;
}
push_down(root,R-L+1);
int mid=L+((R-L)>>1);
if(l<=mid)
change(l,r,L,mid,root<<1);
if(r>mid)
change(l,r,mid+1,R,root<<1|1);
push_node(root);
return;
}
int query(int l,int r,int L,int R,int root)
{
if(l<=L&&R<=r)
{
return sum[root];
}
int ret=0;
push_down(root,R-L+1);
int mid=L+((R-L)>>1);
if(l<=mid)
ret+=query(l,r,L,mid,root<<1);
if(r>mid)
ret+=query(l,r,mid+1,R,root<<1|1);
push_node(root);
    return ret;
}
int main()
{
tree_no=0;
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
int x;
scanf("%d",&x);
g[x].push_back(i);
g[i].push_back(x);
}
for(int i=1;i<=n;i++)
scanf("%d",&t[i]);
dfs(1,0);
build(1,n,1);
cin>>q;
while(q--)
{
string s;
int x;
cin>>s>>x;
if(s[0]=='g')
{
int ans=query(l[x],r[x],1,n,1);
cout<<ans<<endl;
}
else
{
change(l[x],r[x],1,n,1);
}
}
return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注