题解：【CTS2022】独立集问题

iyaang · 2023-04-24 21:20:27 · 题解

心动的阅读体验

题目链接

来自 2023SDPT-Round1-Day4 课上 Qingyu 的讲解。

考虑对于一个点多次操作会发生什么？第一次操作会将周围的点的权值吸过来，自己对答案的贡献乘 -1，周围的点的贡献乘 +1，得到新的权值 a_x' = \pm a_x \mp \sum_{y \in son_x} a_y；再一次操作，我们可以将这个新的贡献取反。于是我们可以得到如果一个点被操作，那么他最后的贡献可以自由控制符号，答案求的是最大值，|a_i'| 的绝对值号可以拆开算贡献。

来点暴力 DP。很自然能够想到分成三种进行讨论：自己的值被父亲吸走，自己的值被儿子吸走，自己吸走别人的值。那么不妨设 f_{x,0/1/2,0/1} 记录，第一维是节点编号，第二维是三种情况讨论，第三维是当前节点是否吸走了父亲的值，DP 的值即为按这种方式转移能够得到的最大答案。接下来考虑如何转移：

首先我们钦定如果是 f_{x,0,0/1} 即被父亲吸走后，依旧可以操控这个状态来继续吸取儿子；如果是 f_{x,1,0/1} 即被某个儿子吸走后，依旧可以操控这个状态来吸取父亲和其他儿子；
能够注意到 f_{x,0,1} 是没有意义的，因为不可能自己的值被父亲吸走，又吸走了父亲的值。这一维恒为 0；
记 A_x 为 f_{son_x,0,0} \pm val_{son_x},f_{son_x,1,0},f_{son_x,2,0} 中的最大值，B_x 为 f_{son_x,0,0} \pm val_{son_x},f_{son_x,1,0}，C_x 为 f_{son_x,1,1},f_{son_x,2,1}，其中 f_{son_x,0,0} \pm val_x 并不是对两种运算去最值，而是对应第一段中那个式子的两种情况；
对于 f_{x,0,0} 即被父亲吸了，那么儿子对转移过来的值的贡献就是每个儿子的最优值，即 \sum A_{son_x}；
对于 f_{son_x,1,0/1} 即被儿子吸了的，我们在决策被哪一个儿子吸收的时候，贪心的看一下不加那个儿子的权值最优即可，去掉的儿子即为 A_{son_x} - C_{son_x} 最小的那个，将该值即为 D_i，儿子对转移过来的值的贡献即为 \sum A_{son_x} - D_i。吸了父亲的情况再加上对应情况的父亲的权值即可；
对于 f_{son_x,2,0/1} 即自己吸收的，儿子对转移过来的值的贡献即为 \sum B_{son_x}，最后还要对应的加或减去自身的权值。吸了父亲的情况再加上对应情况的父亲的权值即可；
对于每个点，分别记录一遍两种情况的 A_x,B_x,C_x，再加上对应计算方式（第一段中的式子）的本身节点的权值，看一看选取哪个最优；
最后的答案即为 \max{(f_{root,1,0},f_{root,2,0})}。

由此我们只需要遍历树一遍，记录和转移 DP 数组，细节还是很多的。时间复杂度为 \mathcal O(n)。

upd 2023.7.23 感谢 @trsins，修改了两个错误的式子。

#include<bits/stdc++.h>
#define ld long double 
#define ull unsigned long long
#define int long long
#define pb push_back
#define mp make_pair
using namespace std;

inline int read()
{
    int s=0,w=1; char c=getchar();
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return s*w;
}
inline void write(int x,char ch)
{
    if(x<0) x=-x,putchar('-');
    static char stk[25]; int top=0;
    do {stk[top++]=x%10+'0',x/=10;} while(x);
    while(top) putchar(stk[--top]);
    putchar(ch);
    return;
}

namespace MyTool
{
    static const int Mod=1e9+7;
    template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    inline int  Max(int a,int b)   {return (b&((a-b)>>63))|(a&(~(a-b)>>63));}
    inline int  Min(int a,int b)   {return (a&((a-b)>>63))|(a&(~(a-b)>>63));}
    template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
    template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
    inline int  Abs(int a) {return (a^(a>>63))-(a>>63);}
    inline void Madd(int &a,int b) {a=a+b>Mod?a+b-Mod:a+b;}
    inline void Mdel(int &a,int b) {a=a-b<0?a-b+Mod:a-b;}
    inline void Mmul(int &a,int b) {a=1ll*a*b%Mod;}
    inline void Mmod(int &a) {a=(a%Mod+Mod)%Mod;}
    inline int  Cadd(int a,int b)  {return a+b>=Mod?a+b-Mod:a+b;}
    inline int  Cdel(int a,int b)  {return a-b<0?a-b+Mod:a-b;}
    inline int  Cmul(int a,int b)  {return a*b%Mod;}
    inline int  Cmod(int a)  {return (a%Mod+Mod)%Mod;}
    inline int  gcd(int a,int b)   {return b?gcd(b,a%b):a;}
    inline int  qpow(int a,int b)  {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    inline int  qmul(int a,int b)  {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    template<typename T> inline T pow(T x)    {return x*x;}
}
using namespace MyTool;

inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    return;
}

bool Mbe;

namespace LgxTpre
{
    static const int MAX=500000;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=998244353;
    static const int bas=131;

    int n,val[MAX],fa[MAX];
    vector<int> G[MAX];

    int f[MAX][3][2];
    void dfs(int now)
    {
        int zsum1=0,zsum2=0,zmix=INF;
        int fsum1=0,fsum2=0,fmix=INF; 
        for(auto to:G[now]) 
        {
            dfs(to);
            zsum1+=max({f[to][0][0]+val[to],f[to][1][0],f[to][2][0]});
            zsum2+=max({f[to][0][0]+val[to],f[to][1][0]});
            cmin(zmix,max({f[to][0][0]+val[to],f[to][1][0],f[to][2][0]})-max({f[to][1][1],f[to][2][1]}));
            fsum1+=max({f[to][0][0]-val[to],f[to][1][0],f[to][2][0]});
            fsum2+=max({f[to][0][0]-val[to],f[to][1][0]});
            cmin(fmix,max({f[to][0][0]-val[to],f[to][1][0],f[to][2][0]})-max({f[to][1][1],f[to][2][1]}));
        }
        f[now][0][0]=max(zsum1,fsum1);
        f[now][1][0]=max(zsum1-zmix,fsum1-fmix);
        f[now][1][1]=max(zsum1-zmix+val[fa[now]],fsum1-fmix-val[fa[now]]);
        f[now][2][0]=max(zsum2-val[now],fsum2+val[now]);
        f[now][2][1]=max(zsum2-val[now]+val[fa[now]],fsum2+val[now]-val[fa[now]]);
        return;
    }

    inline void lmy_forever()
    {
        n=read();
        for(int i=1;i<=n;++i) val[i]=read();
        for(int i=2;i<=n;++i) fa[i]=read(),G[fa[i]].pb(i);
        dfs(1);
        write(max({f[1][1][0],f[1][2][0]}),'\n');
        return;
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",(&Med-&Mbe)/1048576.0);
    LgxTpre::lmy_forever();  
    cerr<<1e3*clock()/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}

题解：【CTS2022】 独立集问题

题解：【CTS2022】独立集问题