[EC Final 2022] Coloring 题解

· · 题解

连边 a_i\to i 建出外向基环树，方便接下来的处理。

先考虑如果 s 不在环上怎么做，即解决树的问题。不妨认为 s 为根；对于不是 s 的每个结点 u，考虑其颜色改变的次数 c_u，那么它的儿子 k 必然满足 c_u\ge c_k（因为对于一个结点，如果在连续的两次操作中给了它相同的颜色，那么后面一个操作就没有意义）；结点 s 特殊一些，它的儿子只需满足 c_u+1\ge c_k。

于是做树形 DP，设 f_{u,i} 表示结点 u 颜色被改变了 i 次，u 子树能产生的最大得分。初始时 f_{u,i}=((i+[u=s])\bmod 2)\cdot w_u-i\cdot p_u（其中 [] 表示艾弗森括号），转移时对于每个儿子 k，f_{u,i}\gets f_{u,i}+\max\limits_{j=0}^{i+[u=s]}f_{k,j}。

可以针对这个 DP 的过程进行操作的构造，所以它的正确性并没有问题。使用前缀 \max 优化即可做到 O(n^2)。

于是对于 s 不在环上的情况，答案即为 \max\limits_{j=0}^n f_{s,j}。进一步地，可以证明答案即为 \max\{f_{s,0},f_{s,1}\}，只需要考虑 DP 的过程，其他情况都可以调整成更优的。

对于 s 在环上且环长 =2 的情况，令环上另一个点为 t，答案为 \max\{f_{s,0}+f_{t,0},f_{s,1}+f_{t,0},f_{s,0}+f_{t,1}\}。

对于 s 在环上且环长 >2 的情况，同样地令 c_u 表示点 u 颜色改变的次数，并且将 c_s 视为 1。令该环为 \mathrm{cyc}_1(=s)\to\mathrm{cyc}_2\to\cdots\to\mathrm{cyc}_k(=t)，那么有如下的结论：

前者是显然的，因为一个结点的前驱没法给它提供更多的次数。后者只需考虑最大化不等式左边的值，让 t 把颜色 0 推给 s，这样 c_s=2，而其他点 c_{\mathrm{cyc}_i}=0，此时差为 2：想让 c_s 变得更大，需要把 s 最开始时的颜色 1 在环上推一圈，此时其他的 c_{\mathrm{cyc}_i} 变为 1，差仍然为 2，所以后者是正确的。

于是枚举 c_s=r=1,2,\ldots,n+1，再做一个 DP g_{i,j}(0\le j\le 2) 表示考虑了环上前 i 个点，c_{\mathrm{cyc}_i}=r-j 的最大答案（对于环上每个点做树形 DP 求解）。于是初始状态为 g_{1,0}=f_{s,r-1}（-1 是因为将 c_s 的初始状态视为 1，所以应该减掉），g_{1,1}=g_{1,2}=-\infin。对于 i>1 有转移 g_{i,j}=f_{\mathrm{cyc}_i,r-j}+\max\limits_{k=0}^j g_{i-1,k}。在这些 r 中取答案最大的即可。

时间复杂度 O(n^2)，可以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll I=1e18;
inline void chmax(ll &x,ll y){if(y>x)x=y;}
vector<int> find_cycle(vector<int> a){
  int x=0; vector<bool> b(a.size());
  while(!b[x])b[x]=true,x=a[x];
  fill(b.begin(),b.end(),false);
  vector<int> c;
  while(!b[x])c.emplace_back(x),b[x]=true,x=a[x];
  return c;
} // 基环树找环
int main(){
  ios::sync_with_stdio(false);
  int n,s; cin>>n>>s,s--;
  vector<int> w(n),p(n),a(n);
  for(auto &i:w)cin>>i;
  for(auto &i:p)cin>>i;
  for(auto &i:a)cin>>i,i--;
  vector<vector<int> > g(n);
  for(int i=0;i<n;i++)
    g[a[i]].emplace_back(i);
  vector<int> c=find_cycle(a);
  reverse(c.begin(),c.end());
  vector<bool> b(n);
  for(int i:c)b[i]=true;
  vector f(n,vector<ll>(n+2));
  function<void(int)> dfs=[&](int u){
    for(int i=0;i<=n;i++)
      f[u][i]=(i&1^(u==s)?w[u]:0)-(ll)i*p[u];
    f[u][n+1]=-I;
    for(int i:g[u])
      if(!b[i]){
        dfs(i); ll mx=-I;
        for(int j=0;j<=n;j++){
          chmax(mx,f[i][j]);
          f[u][j]+=max(mx,u==s?f[i][j+1]:-I);
        } // 前缀和优化转移
      }
  }; // 进行树形 DP
  if(b[s]){
    rotate(c.begin(),find(c.begin(),c.end(),s),c.end());
    // 使 s 成为环上第一个点
    for(int i:c)dfs(i); // 对于环上每个点跑树形 DP
    if(c.size()==2)cout<<max({f[s][0]+f[c[1]][0],f[s][0]+f[c[1]][1],f[s][1]+f[c[1]][0]})<<endl,exit(0);
    // 注意特判 k=2
    ll w=-I;
    for(int r=1;r<=n+1;r++){
      vector g(c.size(),vector<ll>(3,-I));
      g[0][0]=f[s][r-1];
      for(int i=1;i<c.size();i++){
        chmax(g[i][0],g[i-1][0]+f[c[i]][r]);
        chmax(g[i][1],max(g[i-1][0],g[i-1][1])+f[c[i]][r-1]);
        if(r>1)chmax(g[i][2],max({g[i-1][0],g[i-1][1],g[i-1][2]})+f[c[i]][r-2]);
      } // 在环上跑外层 DP
      chmax(w,*max_element(g.back().begin(),g.back().end()));
    }
    cout<<w<<endl;
  }
  else dfs(s),cout<<max(f[s][0],f[s][1])<<endl;
  return 0;
}