自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:07，当前版本为作者最后更新于2025-03-12 10:50:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

连边 $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)$，那么有如下的结论：

• $c_{\mathrm{cyc}_{i+1}}\le c_{\mathrm{cyc}_i}$；
• $c_s-c_t\le 2$。

前者是显然的，因为一个结点的前驱没法给它提供更多的次数。后者只需考虑最大化不等式左边的值，让 $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;
}