自动搬运

查看原文

来自洛谷，原作者为

	leo120306 这是一位野生的七年级蒟蒻 || 用三年筑就一个奇迹，用三日创造一个笑话

搬运于2025-08-24 23:10:47，当前版本为作者最后更新于2025-03-09 18:45:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意简述

给定一颗无根树/基环树，有点权，求点权和最大的简单路径的点权和。

分析

1. $m=n-1$

树上求最小点权和路径很简单，树形 dp 一下就好了。

void dfs(int u,int fa){
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		ans[u]=max(ans[u],dp[u]+dp[v]);
		dp[u]=max(dp[u],dp[v]+a[u]);
	}
}

2. $m=n$

本题最复杂的部分。首先，对于基环树，我们需要得到这个环，搜索一下即可。

int vi[N], // 标记
vis[N],viscnt; // 存储正在递归的索引

vector<int>ring; // 存储环上的点编号
int f=0;

void dfs2(int u,int fa){
	if(f)return;
	if(vi[u]){
		int las=viscnt;
		while(vis[viscnt]!=u)
			ring.push_back(vis[viscnt]),viscnt--;
		ring.push_back(u);
		viscnt=las;
		f=1;
		return;
	}
	vi[u]=1;
	vis[++viscnt]=u;
	for (int v:g[u]){
		if(v==fa)continue;
		dfs2(v,u);
	}
	viscnt--;
	vi[u]=0;
}

然后考虑基环树直径的形式。以环上每一个结点为根分别拆分子树，不难得出有两种可能：直径是子树的直径，或者是一个子树以根为端点的极长链——环——另一个子树以根为端点的极长链。

对于第一种情况，分别按 $m=n-1$ 的方法求出子树直径，再取最大值。

对于第二种情况，设环上有 $x$ 个结点。不妨先断环为链，环上第 $i$ 个结点的编号为 $r_i\ (1 \le i \le 2x)$，环上结点编号 $r_i$ 的子树以根为端点的极长链长度为 $dp_{r_i}$。我们需要做的就是求环上的这段路径长度。因此作关于环上点权的前缀和，记作 $s_i (1 \le i \le 2x)$。可推出我们需要求：

$$\max\{ s_{i-1} - s_j + dp_{r_i} + dp_{r_j} \} \quad(i-1 \ge j,i-j < cnt) $$

枚举 $i$，单调队列维护 $- s_j + dp_{r_j}$ 即可。

求 $dp$ 时间复杂度 $O(n)$，断环为链+前缀和时间复杂度 $O(n)$，单队时间复杂度 $O(n)$，总复杂度 $O(n)$，可通过。

实现

说句闲话：记得断环为链数组开两倍。记得开 long long。

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
#define Mod 1000000007
#define N 200005
#define int ll

int n,m;
int dp[N],ans[N];
vector<int>g[N];
int a[N];
int vi[N],vis[N],viscnt,onring[N],sr[2*N];
vector<int>ring;


void dfs(int u,int fa){
	for(int v:g[u]){
		if(v==fa||onring[v])continue;
		dfs(v,u);
		ans[u]=max(ans[u],dp[u]+dp[v]);
		dp[u]=max(dp[u],dp[v]+a[u]);
	}
}

int f=0;

void dfs2(int u,int fa){
	if(f)return;
	if(vi[u]){
		int las=viscnt;
		while(vis[viscnt]!=u)
			ring.push_back(vis[viscnt]),viscnt--;
		ring.push_back(u);
		viscnt=las;
		f=1;
		return;
	}
	vi[u]=1;
	vis[++viscnt]=u;
	for (int v:g[u]){
		if(v==fa)continue;
		dfs2(v,u);
	}
	viscnt--;
	vi[u]=0;
}

int q[N],tail=0,head=1;

signed main(){
	memset(ans,0xc0,sizeof(ans));
	memset(dp,0xc0,sizeof(ans));
	
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	int d=-1e9; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i]=a[i];
		d=max(d,a[i]);
	}
	
	if(m==n-1){
		dfs(1,0);
		for(int i=1;i<=n;i++)
			d=max(d,ans[i]);
		cout<<d<<endl;
		return 0; 
	}
	
	dfs2(1,0);
	int cnt=ring.size();
	ring.insert(ring.begin(),0);
	for(int i=1;i<=cnt;i++)
		onring[ring[i]]=i+1,ring.push_back(ring[i]);
	ring.push_back(0);
	for(int i=1;i<=2*cnt;i++){
		sr[i]=sr[i-1]+a[ring[i]];
	}
	for(int i=1;i<=cnt;i++)
		dfs(ring[i],0);
	
	for(int i=1;i<=2*cnt;i++){
		while(head<=tail&&q[head]<=i-cnt)head++;
		if(head<=tail&&i-1>=q[head]){
			d=max(d,sr[i-1]-sr[q[head]] + dp[ring[i]]+dp[ring[q[head]]]);
		}
		while(head<=tail&&dp[ring[q[tail]]]-sr[q[tail]] <= dp[ring[i]]-sr[i])tail--;
		q[++tail]=i;
	}
	
	for(int i=1;i<=n;i++)
		d=max(d,ans[i]);
	
	cout<<d<<endl;
	
	return 0;
}