题解：P8877 [传智杯 #5 初赛] I-不散的宴会

· · 题解

题解：P8877 [传智杯 #5 初赛] I-不散的宴会

题目大意

给你很多点，按照三角形排列。每一列的点有直接的边相连。从第 2 层开始，每一层的最后一个点，都会向上一层的一个点连边。

分析

容易证明，连出来的结构是一颗树。可以发现，在 i 层之前的结构就已经是一个连通的树了，归纳证明即可。

但是对于普通树上最大权独立集的做法显然不能直接放到此题上。这道题的点数可以到达 N^2 的量级，直接做就爆炸了。

那么，显然说明这颗树上有部分结构是可以快速计算的。观察到这个树是许多链相连，那么最重要的点显然是链之间相连的点。就是那些三度点，其余的二度点全都构成的是链。并且，三度点的个数就是 N-1，比较小。

于是有一个显然的思路就是对三度点和最高点还有最底层的点建虚树。本题的虚树建立的方法也更加简单，因为每个点之间的 \operatorname{lca} 也在虚树内。我们记录下每一列的点需要往哪里连，并且实时更新就可以建出虚树。

剩下的就是快速计算虚树上点之间被忽略的链就完成了。考虑到这些链其实是 R 序列或者 R 序列所有数取反的一个子区间。

注意到是 01 序列，权值为 0 点相当于可以分割他两边的序列变为独立的。那么只需要考虑左部点所在的极长连续 1 序列的贡献先减去，就可以差分了，之后再将这部分的贡献加回来就计算出了区间的最大点权独立集。

CODE

#include <bits/stdc++.h>
// #define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mkp make_pair
#define vi vector<int>
#define pb emplace_back
using namespace std;
constexpr int N=1e6+5;
typedef long long ll;
constexpr ll inf=1e18;
int n,r[N],c[N],ir[N];
struct node{
    int f[N][2],h[N],p[N],val[N];
    node()=default;
    void init(int r[])
    {
        for(int i=1;i<=n;i++)
        {
            f[i][1]=f[i-1][0]+r[i];
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            h[i]=max(f[i][1],f[i][0]);
            val[i]=r[i];
        }
        for(int i=n,fl=0,las=-1;i>=1;i--)
        {
            if(!r[i])
                p[i]=i,fl=0;
            else
            {
                if(!fl)fl=1,las=i;
                p[i]=las;
            }
        }
    }
    ll calc(int l,int r)
    {
        if(r-l+1<=-2)return -inf;
        if(r-l+1<=0)return 0;
        return h[r]-h[min(r,p[l])]+(val[l]?(min(r,p[l])-l)/2+1:0);
    }
}v[2];
int a[N];
int idx;
pii id[N<<1];
vi e[N<<1];
int las[N];
ll f[N<<1][2];
void dfs(int u)
{
    for(auto v:e[u])
    {
        dfs(v);
        ll mx=0;
        mx=::v[c[id[v].se]].calc(id[u].fi+1,id[v].fi-1)+f[v][0];
        mx=max(mx,::v[c[id[v].se]].calc(id[u].fi+1,id[v].fi-2)+f[v][1]);
        f[u][0]+=mx;
        // cout<<"v:"<<v<<' '<<f[v][0]<<' '<<f[v][1]<<'\n';
        // cout<<"mx1:"<<mx<<' ';
        mx=::v[c[id[v].se]].calc(id[u].fi+2,id[v].fi-1)+f[v][0];
        mx=max(mx,::v[c[id[v].se]].calc(id[u].fi+2,id[v].fi-2)+f[v][1]);
        // cout<<"mx2:"<<mx<<'\n';
        f[u][1]+=mx;
    }
    f[u][1]+=r[id[u].fi]^c[id[u].se];
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
    freopen("wa.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>r[i],ir[i]=(r[i]^1);
    v[0].init(r);
    v[1].init(ir);
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=2;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++)
    {
        id[++idx]=mkp(i-1,a[i]);
        if(las[a[i]])e[las[a[i]]].pb(idx);
        las[a[i]]=las[i]=idx;
    }
    for(int i=1;i<=n;i++)
        id[++idx]=mkp(n,i),e[las[i]].pb(idx);
    // for(int i=1;i<=idx;i++)
    // {
    //  for(auto v:e[i])
    //  {
    //      cerr<<i<<' '<<v<<'\n';
    //  }
    // }
    dfs(1);
    cout<<max(f[1][0],f[1][1]);
    return 0;
}

TIPS

注意答案范围需要开 long long。计算区间独立集时，可以钦定为 0 的点连续 1 段的最右端点为自己。然后左端点如果为 0 就不需要计算连续 1 段的附加贡献了。