题解：P11850 [TOIP 2023] 关卡地图

· · 题解

前言：

题解只有一篇，所以写一篇。

分析：

此题要求我们求树的直径，但是边权变成了点权。

但是没有关系，让我们重新思考。

首先考虑树的子任务：设 dp_{now} 表示以 now 这个点为根的子树，且最长链必经过 now 的最长链长度，f_{now} 表示在以 now 为根的子树中，经过 now，但是不计算 now 点权值的最长链。

那么 dp_{now} 的转移是简单的，分以下三种讨论：

那么你就可以转移出 dp_{now} 了。f_{now} 的转移也差不多。

    f[now] = 0 , dp[now] = a[now] , anstr = max (anstr , dp[now]);
    for (auto x : g[now]) {
        if (x == fa || !tag[x]) continue;
        dfs (x , now) ;
        dp[now] = max (dp[now] , max (f[x] + f[now] + a[now] + a[x] , max (f[x] , f[now]) + a[x] + a[now]) ) ;
        f[now] = max ( f[x] + a[x] , max (f[now] , a[x]) ) , anstr = max (anstr , dp[now]);
    }

然后你就可以通过树的子任务了。

考虑有环的一般情况：我们讨论以下两种：

那么对于经过环的情况，我们考虑怎么表示它的直径。对于环上两个不同点 i,j，我们把路径拆成三段：

写出来大概长这样：

T=\max_{i\ne j}{(f_i+f_j+dis_{i,j})}

其中 T 就是答案。

这个 dis_{i,j} 我们再做一个前缀和，就变成了 sum_j-sum_{i-1}。当然路径有两条，记环上点权总和为 S，则两条路径权值分别为 S-(sum_j-sum_{i-1})+a_j+a_i 和 sum_j-sum_{i-1}。

然后你对于环扫两遍，每次维护一种路径就可以了。

# include <bits/stdc++.h>
# define int long long
# define pb push_back
using namespace std;
const int N = 3e5 + 5;
int n , m , a[N] , deg[N] , tag[N] , f[N] , dp[N] , fuck[N] , id[N] , cur , ans = -9e18 , sum[N] , anstr = -9e18;
vector <int> g[N];
vector <int> loop;
void dfs (int now , int fa) {
    f[now] = 0 , dp[now] = a[now] , anstr = max (anstr , dp[now]);
    for (auto x : g[now]) {
        if (x == fa || !tag[x]) continue;
        dfs (x , now) ;
        dp[now] = max (dp[now] , max (f[x] + f[now] + a[now] + a[x] , max (f[x] , f[now]) + a[x] + a[now]) ) ;
        f[now] = max ( f[x] + a[x] , max (f[now] , a[x]) ) , anstr = max (anstr , dp[now]);
    }
    return void();
}
int sol (int x) {
    sum[0] = 0; int tot = 0 , maxx = -9e18 , res = -9e18;
    for (int i = 1;i < loop.size();++i) sum[i] = sum[i - 1] + a[loop[i]];
    tot = sum[(int)loop.size() - 1] ; for (int i = 1;i < loop.size();++i) res = max (res , sum[i] + f[loop[i]] + maxx) , maxx = max (maxx , f[loop[i]] - sum[i - 1]); maxx = -9e18;
    for (int i = 1;i < loop.size();++i) res = max (res , -sum[i] + f[loop[i]] + maxx + a[loop[i]]) , maxx = max (maxx , f[loop[i]] + sum[i - 1] + tot + a[loop[i]]);
    return res;
}
signed main () {
    cin >> n >> m; for (int i = 1;i <= m;++i) { int u , v; cin >> u >> v , g[u].pb (v) , g[v].pb (u) , deg[u] ++ , deg[v] ++ ; }
    for (int i = 1;i <= n;++i) cin >> a[i]; queue <int> q; for (int i = 1;i <= n;++i) if (deg[i] == 1) q.push (i);
    while (!q.empty()) { int now = q.front(); q.pop() , tag[now] = 1; for (auto x : g[now]) if (--deg[x] == 1) q.push (x);  }
    if (m == n - 1) {dfs (1 , 1) ; return cout << anstr << '\n' , 0; }
    for (int i = 1;i <= n;++i) if (!tag[i]) dfs (i , i); loop.pb (0);
    for (int i = 1;i <= n;++i) if (!tag[i]) {while (i) { for (auto x : g[i]) if (!tag[x] && !fuck[x]) {fuck[i] = x; break;} id[i] = ++cur , loop.pb (i) , i = fuck[i]; } break;} 
    cout << max (sol(-1) , anstr) << "\n"; return 0;
}