题解：P10722 [GESP202406 六级] 二叉树

fangminding · 2024-07-10 09:52:41 · 题解

这里来提供一种不同的树状数组加 dfs 序的解法，复杂度较劣，但可以通过。

注意到操作是对树上一点的子树进行的，故想到使用 dfs 序来维护（dfs 序有一个很好的性质，一个点及其子树上所有点在 dfs 序中是连续的，非常方便进行子树操作）。

而同一个点每修改两次就会变回原来的颜色，故用差分树状数组维护每个点的更改次数即可。

最后输出时判断奇偶性并与初始颜色进行计算即可得到结果。

不会差分树状数组的点这里。

完整代码：

#include <bits/stdc++.h>
using namespace std;
vector<int>son[500005];
int fa[500005],frt[500005],dfsx[500005],cnt,n,q,siz[500005],tree[500005];
int low(int a)
{
    return a&(-a);
}
void add(int ass,int k)
{
    while(ass<500005)
    {
        tree[ass]+=k;
        ass+=low(ass);
    }
}
int ask(int rit)
{
    int ans=0;
    while(rit>0)
    {
        ans+=tree[rit];
        rit-=low(rit);
    }
    return ans;
}
void dfs(int u)
{
    dfsx[u]=++cnt;
    for(int i = 0;i <son[u].size();i++)
        dfs(son[u][i]);
    siz[u]=1;
    for(int i = 0;i <son[u].size();i++)
        siz[u]+=siz[son[u][i]];
    return;
}
signed main()
{
    cin>>n;
    for(int i = 2;i <=n;i++)
        cin>>fa[i];
    char ct;
    for(int i = 1;i <=n;i++)
    {
        cin>>ct;
        frt[i]=ct-'0';
    }
    for(int i = 2;i <=n;i++)
        son[fa[i]].push_back(i);
    dfs(1);
    cin>>q;
    for(int i = 1;i <=q;i++)
    {
        int t;
        cin>>t;
        add(dfsx[t],1);
        add(dfsx[t]+siz[t],-11);
    }
    for(int i = 1;i <=n;i++)
        cout<<(frt[i]+ask(dfsx[i])+100000000)%2;
    return 0;
}

AC 记录(巨慢无比)