EC-Final 2022 (UCup Stage 11) A.Coloring

· · 题解

晃了一圈没找到题解，官方题解又简略的很，因此记之。

首先对所有 a_i 向 i 连边可构成基环外向树森林，此时若有边 (u,v) 即为可以进行操作 c_u := c_v，就是能将 c_u 赋值给 c_v。

先不考虑这个 s 的位置，考虑如果有一个环上的点 rt，它颜色的改变对子树的影响。

由于上面的连边方式，每次 rt 都能将子树内任意一个与 rt 连通的连通块染成和 rt 一样的颜色。而为了最优，这次染色一定不会把上次染的全部覆盖掉（要不然上一次就白干了），因此最终子树内一定是 01 分层的情况，如下图：

其中 rt=1。注意分层并不是严格按照深度，而是按照每次染的点决定的。

显然越多的变换次数会给子树带来更多可能性，当也会增加 p 的消耗。于是我们考虑在每棵子树都 dp 出 dp[u][i] 表示以 u 为根的子树， u 变换了 i 次后 u 的子树权值最大值（同时对 rt 进行环上的贡献提前计算）。

需要对 s 进行特殊处理。实现不难，具体的看代码。此处复杂度 O(n^2)。

如果 s 不在环上，显然 ans=\max(dp[s][0],dp[s][1]) 就完事了。接下来考虑 s 在环上的部分。

记 r_i 为环上点 i 01 变换了几次。若将 s 作为环的起点且 r_s 视作初始为 1，则有结论：从 s 开始按照边的顺序，r 单调不增且极差 \le 2。请自己手摸尝试证明或感性理解。

而且反过来，任意一组满足上述条件的 r 都对应了一个变换结果（不一定唯一）。还是请自己手摸尝试感性理解。

因此在环上，我们可枚举 r_s，并进行 dp，f[i][0/1/2] 表示环上第 i 个点的 r 为 r_s/r_s-1/r_s-2 时的最大值。不难写。

做完了，有一些细节，然后是代码：


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
inline ll rd(){
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
#define d rd()
ll n,m,s;
ll w[5010],p[5010];
vector<ll>e[5010],ee[5010];
ll in[5010];
bool vis[5010];
queue<ll>q;
ll dis[5010];
ll dp[5010][5010];
void dfs(ll u){
    f(i,0,n){
        ll x=(i&1);if(u==s)x^=1;
        dp[u][i]=x*w[u]-i*p[u];
    }for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(!vis[v])continue;
        dfs(v);ll mx=dp[v][0];
        f(j,0,n)dp[u][j]+=(u==s?max(mx,dp[v][j+1]):mx),mx=max(mx,dp[v][j+1]);
    }dp[u][n+1]=-1e18;
}
ll lp[5010],cl;
void dfl(ll u){
    if(u==s&&cl)return;
    lp[++cl]=u;
    for(int i=0;i<e[u].size();i++){
        ll v=e[u][i];if(vis[v])continue;
        dfl(v);
    }
}
ll sum[5010][5010];
ll f[5010][3],res=-1e18;
#define Max(a,b) (a>b?a:b)
int main(){
    n=d,s=d;f(i,1,n)w[i]=d;f(i,1,n)p[i]=d;
    f(i,1,n){
        ll x=d;e[x].push_back(i);
        ee[i].push_back(x);in[x]++;
    }f(i,1,n)if(!in[i])q.push(i);
    while(!q.empty()){
        ll u=q.front();q.pop();
        vis[u]=1;for(int i=0;i<ee[u].size();i++){
            ll v=ee[u][i];if(in[v]&&!(--in[v]))q.push(v);
        }
    }if(vis[s]){
        dfs(s);cout<<max(dp[s][0],dp[s][1]);return 0;
    }dfl(s);f(i,1,cl)dfs(lp[i]);
    if(cl==2){
        cout<<max(dp[s][0]+dp[lp[2]][1],max(dp[s][1]+dp[lp[2]][0],dp[s][0]+dp[lp[2]][0]));
        return 0;
    }
    f(k,1,n+1){
        f[1][0]=dp[s][k-1],f[1][1]=f[1][2]=-1e18;
        f(i,2,cl){
            f[i][0]=f[i-1][0]+dp[lp[i]][k];
            f[i][1]=max(f[i-1][0],f[i-1][1])+dp[lp[i]][k-1];
            if(k>=2)f[i][2]=max(f[i-1][0],max(f[i-1][1],f[i-1][2]))+dp[lp[i]][k-2];
            if(f[i][0]<-1e18)f[i][0]=-1e18;
            if(f[i][1]<-1e18)f[i][1]=-1e18;
            if(f[i][2]<-1e18)f[i][2]=-1e18;
        }res=max(res,max(f[cl][1],f[cl][0]));
        if(k>=2)res=max(res,f[cl][2]);
    }cout<<res;
    return 0;
}