P9846 [ICPC 2021 Nanjing R] Paimons Tree

派蒙题。

首先发现填完权值后的直接必定是原树直径中的某一条，但是无法确定是其中哪一条，所以这个发现是没用的/tx。

发现按照题目的染色方法，每个时刻染色的边必然为一条路径。

观察到 \(n\) 的范围很小，首先考虑枚举最终结果直径。

钦定直径后，把直接提出来，设计状态 \(f_{l,r,k}\) 表示当前染了直径上 \([l,r]\) 路径，一共操作了 \(k\) 次，路径上最大权值和。下一步操作有两种选择：

1. 拓展至 \(f_{l-1,r,k+1}\) 或 \(f_{l,r+1,k+1}\) 获得 \(a_i\) 的贡献。

2. 将 \(a_i\) 放到不在这条直径上的边，将直径上的边留给后面更大的权值，即更新 \(f_{l,r,k+1}\)。

第一种操作就不说了，第二种操作发现能舍弃的边数为 \([l,r]\) 路径内每个点不经过直径上的边可达的边数。

因为钦定了直径所以能舍弃边数是好求的。实现上求出以每个点为根时树的 \(siz\)。每次拓展的贡献容易用 \(siz\) 表示。

枚举直径是 \(O(n^2)\)，dp 状态为 \(O(n^3)\)，转移 \(O(1)\)，所以总复杂度为 \(O(n^5)\)。

发现炸了。显然有很多状态 \(f_{l,r,k}\) 会在很多条直径中出现。

考虑不钦定直径，设计状态 \(f_{l,r,k}\) 表示染了 \([l,r]\) 的路径，一共操作 \(k\) 次，路径上最大权值和。

于是状态是 \(O(n^3)\)，转移 \(O(1)\)，总复杂度 \(O(n^3)\)。

但是出现了新的问题，一开始容易计算能舍弃的边数是因为钦定了直径知道 \(l,r\) 下一步要向哪个点拓展。但是现在没有钦定直接。

其实只需要把状态改为染了 \((l,r)\) 路径，一共操作 \(k\) 次，路径上最大权值和。

但是就需要讨论转移到 \([l,r),(l,r],[l,r]\) 路径的情况才能得到终止情况。

但是在题解区发现了一个极其优雅的做法，每个叶子额外连接一个虚点，于是终止状态就是两个虚点的 \((u,v)\) 路径的状态。

于是与 \(O(n^5)\) 的转移相同。

#include<bits/stdc++.h>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define tup(x) array<int,(x)>
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
const int N=305;
ll n,a[N],tot,d[N],F[N],lb[N],f[N][N][N],siz[N][N],was[N][N],dis[N][N];
vector<int>e[N];
void add(int u,int v){e[u].pb(v),e[v].pb(u);}
inline void chk(ll &x,ll y){if(y>x)x=y;}
void dfs(int u,int fa){int c=0;for(int v:e[u])if(v^fa) ++c,dfs(v,u);if(c==0)++tot,add(u,n+tot);if(u==1&&c==1)++tot,add(u,n+tot);
}
void get(int u,int fa){d[u]=d[F[u]=fa]+1;int x=lb[fa],y=lb[x];lb[u]=(d[fa]-d[x]==d[x]-d[y]?y:fa);for(int v:e[u])if(v^fa)get(v,u);
}
void Dfs(int u,int fa,int tv){siz[tv][u]=(u<=n);for(int v:e[u])if(v^fa)Dfs(v,u,tv),siz[tv][u]+=siz[tv][v];
}
int lca(int x,int y){if(d[x]<d[y])swap(x,y);while(d[x]>d[y])if(d[lb[x]]>=d[y])x=lb[x];else x=F[x];while(x^y)if(lb[x]^lb[y])x=lb[x],y=lb[y];else x=F[x],y=F[y];return x; 
}
int D(int x,int y){if(~dis[x][y])return dis[x][y];return dis[x][y]=dis[y][x]=d[x]+d[y]-(d[lca(x,y)]<<1);
}
vector<pii>q[N];
inline void UesugiErii(){cin>>n,++n;tot=0;for(int i=1;i<n;i++)cin>>a[i];for(int i=1,u,v;i<n;i++)cin>>u>>v,add(u,v);dfs(1,0),get(1,0);for(int i=1;i<=n+tot;i++)Dfs(i,0,i);for(int i=1;i<=n+tot;i++)for(int j=1,tmp;j<=n+tot;j++)if((tmp=D(i,j)+1)>=3)q[tmp].pb(mp(i,j));for(int i=1;i<=n;i++)for(int x:e[i])for(int y:e[i])if(x^y)f[x][y][0]=0,was[x][y]=n-siz[i][x]-siz[i][y]-1;for(int i=3;i<=n+tot;i++)for(pii j:q[i]){for(int k=0;k<n-1;k++){if(k-i+3<was[j.fi][j.se])chk(f[j.fi][j.se][k+1],f[j.fi][j.se][k]);for(int v:e[j.fi])if(D(v,j.fi)+D(v,j.se)!=D(j.fi,j.se))chk(f[v][j.se][k+1],f[j.fi][j.se][k]+a[k+1]),was[v][j.se]=was[j.fi][j.se]+siz[j.se][j.fi]-siz[j.se][v]-1;for(int v:e[j.se])if(D(v,j.fi)+D(v,j.se)!=D(j.fi,j.se))chk(f[j.fi][v][k+1],f[j.fi][j.se][k]+a[k+1]),was[j.fi][v]=was[j.fi][j.se]+siz[j.fi][j.se]-siz[j.fi][v]-1;}}ll ans=0;for(int i=tot+1;i<=n+tot;i++)for(int j=tot+1;j<=n+tot;j++)chk(ans,f[i][j][n-1]);cout<<ans<<'\n';for(int i=1;i<=n+tot;i++)for(int j=1;j<=n+tot;j++){siz[i][j]=0,dis[i][j]=-1,was[i][j]=0;for(int k=0;k<n;k++)f[i][j][k]=-1e15; }for(int i=1;i<=n+tot;i++)e[i].clear(),q[i].clear();
}
signed main(){//IO();cfast;intz(dis,-1),intz(f,0xcf);int _=1;cin>>_;for(;_;_--)UesugiErii();return 0;
}