题解 P5852 【[USACO19DEC]Bessie's Snow Cow P】

· · 题解

P5852 [USACO19DEC]Bessie's Snow Cow P

给定一棵树，定义一个节点的权值为它染的不同颜色个数（因此一个节点可能有多个颜色）。

维护两个操作： 1.x的子树全染上某种颜色； 2.查询想的子树权值之和；

首先对于每个颜色开一个set，维护子树全部都染上同种颜色的点，且保证不会在同一set中有两个点的子树包含同一点。

通俗解释就是不让一个点被同一颜色染两次。 体现在操作中的实际效应就是加入一个染色时要删掉它子树的所有同色染色信息。

此时需要做的就是在修改的时候同步更新答案。

发现答案分为两部分：
1.祖先的子树染上同种颜色时，附带着我染上了；此时整个子树必定也染上了。
2.我的某个儿子染了，它带动我的一部分子树染了；此时整个子树不一定染上。

于是想到开两颗树状数组：
1.区改单查，维护第一种情况：每次给子树加贡献，每次查单个点的情况。这个情况x与它子树中每个点加的都是一样的，所以可以直接查x的，然后乘子树大小。
2.单改区查，维护第二种情况：每次给单个点加贡献，每次查区间的情况。加的时候我们可以直接把y子树的加的全部加给x那一个点，这样只要查到y那个点就加入了y整个子树的贡献。

这一段的代码如下：

void upd(int x,int d)//修改
{
    A.ins(dfn[x],d);
    A.ins(low[x]+1,-d);//第一种情况：祖先来的贡献
    B.ins(dfn[x],(low[x]-dfn[x]+1)*d);//第二种情况：子树的贡献（注意：因为直接把x子树的贡献加给x了，所以要乘子树大小）
}
int que(int x) {return (low[x]-dfn[x]+1)*A.ask(dfn[x])+B.ask(low[x])-B.ask(dfn[x]);}

整体代码如下：

struct Edge{int to,next;
}a[maxn<<1];
int n,q,dfn[maxn],low[maxn],bc[maxn],h[maxn],dfx,cnt;
void add(int x,int y) {a[++cnt]=(Edge){y,h[x]},h[x]=cnt,a[++cnt]=(Edge){x,h[y]},h[y]=cnt;}
void Dfs(int x)
{
    bc[dfn[x]=++dfx]=x;
    for(int i=h[x];i;i=a[i].next)
        if(!dfn[a[i].to]) Dfs(a[i].to);
    low[x]=dfx;
}
struct Array_Tree{
    int c[maxn];
    void ins(int x,int d) {for(;x<=n;x+=x&-x) c[x]+=d;}
    int ask(int x) {int res=0;for(;x;x-=x&-x) res+=c[x];return res;}
}A,B;
std::set<int> st[maxn];
void upd(int x,int d) {A.ins(dfn[x],d),A.ins(low[x]+1,-d),B.ins(dfn[x],(low[x]-dfn[x]+1)*d);}
signed main()
{
    int x,y;
    n=read(),q=read();
    for(int i=1;i<n;i++) add(read(),read());
    Dfs(1);
    while(q--)
        if(read()==1)
        {
            x=read(),y=read();
            auto it=st[y].upper_bound(dfn[x]);
            if(it!=st[y].begin()&&low[bc[*prev(it)]]>=low[x]) continue;//ancestors
            while(it!=st[y].end()&&(*it)<=low[x]) upd(bc[*it],-1),st[y].erase(it++);
            st[y].insert(dfn[x]),upd(x,1);
        }
        else x=read(),printf("%d\n",(low[x]-dfn[x]+1)*A.ask(dfn[x])+B.ask(low[x])-B.ask(dfn[x]));
    return 0;
}

说了这么多，点个赞再走吧。