洛谷 P6419 [COCI2014-2015#1] Kamp
题意
一颗树 \(n\) 个点，\(n-1\) 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。
有 \(K\) 个人（分布在 \(K\) 个不同的点）要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发，把这 \(K\) 个人分别送回去。
请你回答，对于 \(i=1 \sim n\) ，如果在第 \(i\) 个点举行聚会，司机最少需要多少时间把 \(K\) 个人都送回家。
思路
黑点表示住了人。
若送完最后一个人后再回到起点，答案即为所有黑点到起点的路径并集的边权和。
为了让答案最优，显然删掉最长的那条边。
答案可以表示为：\(2\times \text{sum}-\text{maxdis}\)。
其中 \(\text{sum}\) 可以用换根 DP 简单求出（第一次 DFS 求出根的 \(\text{sum}\)，第二次 DFS 分类讨论增删边权转移至儿子节点）。
重点问题在 \(\text{maxdis}\) 上。
我们考虑原树的一棵子树，满足包含所有黑点，并且所有叶子节点都是黑点。
求出这棵树的直径，\(\text{maxdis}\) 只可能是该点与直径两端点的距离，可以用反证法证明。
代码
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 5e5 + 5;
vector <pii> E[N];
int n, k, siz[N];
bool a[N];
int fa[N][21], de[N];
ll Dis[N], dp[N], dis[N];
void dfs1(int x) {
for (int i = 1; i <= 20; i ++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
siz[x] += a[x];
for (auto e : E[x]) {
ll y = e.fi, z = e.se;
if (y == fa[x][0]) continue;
fa[y][0] = x, de[y] = de[x] + 1;
Dis[y] = Dis[x] + z;
dfs1(y);
siz[x] += siz[y]; // 子树内黑点个数
dp[x] += dp[y];
if (siz[y]) dp[x] += z; // 子树内有,增
}
}
void dfs2(int x) {
for (auto e : E[x]) {
ll y = e.fi, z = e.se;
if (y == fa[x][0]) continue;
if (siz[y] && (k - siz[y])) dp[y] = dp[x]; // 子树内外都有,不增不减
else if (!siz[y] && (k - siz[y])) dp[y] = dp[x] + z; // 子树内没有,增
else if (siz[y] && !(k - siz[y])) dp[y] = dp[x] - z; // 子树外没有,减
dfs2(y);
}
}
int LCA(int x, int y) {
if (de[x] < de[y]) swap(x, y);
for (int i = 20; i >= 0; i --)
if (de[fa[x][i]] >= de[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i --)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
ll getDis(int x, int y) {return Dis[x] + Dis[y] - Dis[LCA(x, y)] * 2ll;}
void dfs3(int x, int FA) {
for (auto e : E[x]) {
ll y = e.fi, z = e.se;
if (y == FA) continue;
dis[y] = dis[x] + z;
dfs3(y, x);
}
}
int main() {
cin >> n >> k;
for (int i = 1, u, v, w; i < n; i ++) {
cin >> u >> v >> w;
E[u].push_back({v, w});
E[v].push_back({u, w});
}
for (int i = 1, x; i <= k; i ++)
cin >> x, a[x] = 1;
dfs1(1); dfs2(1);
int P1 = 0, P2 = 0;
dfs3(1, 0);
for (int i = 1; i <= n; i ++) // 直径
if (a[i] && dis[P1] < dis[i]) P1 = i;
memset(dis, 0, sizeof(dis));
dfs3(P1, 0);
for (int i = 1; i <= n; i ++)
if (a[i] && dis[P2] < dis[i]) P2 = i;
for (int i = 1; i <= n; i ++) // maxdis
dis[i] = max(getDis(i, P1), getDis(i, P2));
for (int i = 1; i <= n; i ++)
cout << dp[i] * 2ll - dis[i] << "\n";
return 0;
}
/*
7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7
*/