首页 题解

# CCPC2022 Guilin G Group Homework

# 题意

给出一个有点权的树，你需要选择两条链，收益为两条链并的权值和减去两条链交的权值和，使得收益最大。

# 题解

如果选择的两条链，交点多于11 个，那么我可以重新选择划分成两条不相交的链，使得收益比原来更大。所以情况只有两种：两条链有一个交点，两条链没有焦点。
两类情况

对于两条链有一个交点的情况，做 dp 计算从每个点延伸出的前四大最长链。这里用 换根dp 实现。首先自下而上计算f0[x][0,1,2,3]f_0[x][0,1,2,3] 表示以11 为根时xx 子树内前四大最长链，再自上而下推出f[x][0,1,2,3]f[x][0,1,2,3] 表示以xx 为根时xx 延伸出的前四大最长链。这里的链长都不包含xx 本身的权值。这样第一种情况的答案就是对每个点 x 的最大f[x][0]+f[x][1]+f[x][2]+f[x][3]f[x][0]+f[x][1]+f[x][2]+f[x][3]。

考虑第二种情况，可以理解为：从xx 子树内选择一条最长链，再从xx 子树外选择一条最长链。这两个链必然是不相交的，并且这样对每个点计算，可以覆盖所有第二类的情况。子树内的最长链g[x]g[x] 很好求，一次 dfs 即可求出。子树外的最长链h[x]h[x] 仍然需要 换根dp 。这里还需要另外一个状态mf[x][0,1]mf[x][0,1] 表示在xx 子树内、xx 的儿子子树最长链的前二大值。
从xx 转移到儿子tttt 时，hh 有可能的取值：

  • 转移自h[x]h[x]
  • 转移自tttt 的兄弟子树 ——xx 的其他儿子子树内最长链。由于tttt 本身可能是xx 的子树最长链，还要再考虑其他子树的最长链。这就是为什么要记录子树最长链的前二大值
  • 转移自经过xx 但不经过子树tttt 的链。我们记录了从xx 延申的前四大最长链，所以很好求得经过xx 的但不经过 tt 的最长链。具体细节需要看代码，有比较巧妙的实现
    第二种情况的答案就是求每个xx 的最大g[x]+h[x]g[x]+h[x]。

总之，这道题目套路性还是很强的，写起来远比想象的要简单一点。有点像是融合了两道换根 dp，状态数有点多。不过两类情况分开考虑的话，还是比较清晰的。

另外，这题还在网上看到了一种完全自下而上转移的做法。大致意思就是，以子数内选择的叶子节点个数划分状态（因为选择的两条链必然对应着四个叶子节点），这样就不再考虑是否有交点，而是在每个节点，考虑其下从几个方向延伸上去。这样做的状态数只有一个 f [x][0,1,2,3]，但是看起来转移挺复杂的。

# 代码

#include<cstdio>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using std::vector;
int read(){
	int out(0),c(getchar());
	for(;c<'0' || c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
		out=(out<<3)+(out<<1)+(c^48);
	return out;
}
void Max(int &a,const int &b){
	if(b>a) a=b;
}
const int MAXN=2e5+10;
const int INF=0x3f3f3f3f;
int N;
int a[MAXN];
vector<int> to[MAXN];
int f[MAXN][4];
int g[MAXN];// 子树直径
int h[MAXN];// 子树外直径
int mf[MAXN][2];// 儿子子树直径前二大
template<const int Sz>
void upd(int f[][Sz],int x,int v){
	for(int i=0;i<Sz;++i)
		if(v>f[x][i])
			std::swap(f[x][i],v);
}
void dfs0(int x,int ff){
	for(int tt:to[x]){
		if(tt==ff)
			continue;
		dfs0(tt,x);
		
		upd<4>(f,x,f[tt][0]+a[tt]);
		Max(g[x],g[tt]);
		upd<2>(mf,x,g[tt]);
	}
	Max(g[x],f[x][0]+f[x][1]+a[x]);
}
void dfs(int x,int ff){
	for(int tt:to[x]){
		if(tt==ff)
			continue;
		Max(h[tt],h[x]);
		Max(h[tt],mf[x][mf[x][0]==g[tt]]);
		int a0=(f[x][0]==f[tt][0]+a[tt]);
		int a1=(f[x][1]==f[tt][0]+a[tt]);
		Max(h[tt],f[x][0+a0]+f[x][1+a0+a1]+a[x]);
		upd<4>(f,tt,f[x][f[x][0]==f[tt][0]+a[tt]]+a[x]);
		
		dfs(tt,x);
	}
}
int main(){
	N=read();
	for(int i=1;i<=N;++i)
		a[i]=read();
	for(int i=1;i<N;++i){
		int x=read(),y=read();
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dfs0(1,0);
	h[1]=-INF;
	dfs(1,0);
	int ans=0;
	
	for(int x=1;x<=N;++x){
		Max(ans,f[x][0]+f[x][1]+f[x][2]+f[x][3]);
		Max(ans,g[x]+h[x]);
		// printf("%d$\n",ans);
	}
	printf("%d\n",ans);
	return 0;
}
  
 更新于   阅读次数  次