【题解】[Coci2015]Kamp 树形 dp 树的直径 bzoj3743 ——quhengyi11

这里是传送门

求每个点遍历一遍关键点的最小长度。

我们先假设，如果它遍历完关键点，要回到原来的点的话，那么经过的每条路径显然是都被经过两次的，因为这里不要求回到原点，并且这样的路径最小的时候生成的路径集合是唯一的，也就是说对于每个原点和所有关键点，经过它们的路径所产生的生成树是固定的，并且每条边被经过两次。

对于这道题，我们可以这样思考，不回到原点，相当于最后一个关键点到原点的那段路可以不走，我们要最小化总路程，也就是最大化最后一个关键点到原点的最大距离。

那暴力算法就是对于每个点，算出它和关键点所对应的生成树，算出它到最远关键点的距离，减一下就行了。

我们考虑如何优化这个算法。

最远的点？我们容易想到直径，我们将关键点相互之间的路径所组成的生成树先算出来，容易知道，这个生成树的直径的两个端点中的其中一个就是所有原树中其它点的最远关键点。否则我们可以反证它不是生成树的直径。

那么算法就显然了，我们可以先将每个点到直径两端点的距离预处理出来记为 $dis1,dis2$，接着枚举每个点 $u$，记生成树的路径和为 $sum$，如果这个点在生成树上，那么答案就是 $sum \times 2 – max(dis1[u],dis2[u])$，如果不在生成树上，我们要在之前预处理一个每个点到生成树任意一个点的最短距离 $dis0$，那么答案就是 $sum \times 2 + dis0[u] \times 2 – max(dis1[u],dis2[u])$

另外 Claris 有一种树 dp 的做法会比较顺思维一点 https://www.cnblogs.com/clrs97/p/4403211.html

代码：

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 10000000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define mod 19260817
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 500005
#define ls (k << 1)
#define rs (k << 1 | 1)
int n, m, head[N], p[N], fa[N], tot, u, v, w;
ll d[3][N], sum;
int val[N];
struct edge{
    int nxt, v, w;
}e[N << 1];
bool vis[N];//是否为生成树上的点
inline void addedge (int u, int v, int w)
{
    e[++tot] = (edge) {head[u], v, w};
    head[u] = tot;
}
inline void dfs (int u, int fath, ll dis[])
{
    fa[u] = fath;
    edge (i, u)
    {
        if (v == fa[u]) continue;
        dis[v] = dis[u] + e[i].w;
        val[v] = e[i].w;
        dfs(v, u, dis);
    }
}
std::queue <int> q;
inline void bfs ()
{
    memset(d[0], 0x3f, sizeof d[0]);
    fo (i, 1, n) if (vis[i]) {d[0][i] = 0; q.push(i);}
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        edge (i, u)
            if (d[0][v] > d[0][u] + e[i].w)
            {
                d[0][v] = d[0][u] + e[i].w;
                q.push(v);
            }
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 2, n)
    {
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w); addedge(v, u, w);
    }
    fo (i, 1, m) {scanf("%d", &p[i]); vis[p[i]] = 1;}
    dfs(p[1], 0, d[0]);
    int lp = 1;
    fo (i, 2, m) if (d[0][lp] < d[0][p[i]]) lp = p[i];
    fo (i, 2, m)
    {
        int u = fa[p[i]];
        sum += val[p[i]];
        while (!vis[u]) {sum += val[u]; vis[u] = 1; u = fa[u];}
    }
    bfs();
    dfs(lp, 0, d[1]);
    int rp = lp;
    fo (i, 1, m) if (d[1][rp] < d[1][p[i]]) rp = p[i];
    dfs(rp, 0, d[2]);
    sum <<= 1;
    fo (i, 1, n)
        printf("%lld\n", sum + (d[0][i] << 1) - std::max(d[1][i], d[2][i]));
    return 0;
}