P6419 [COCI2014-2015#1] Kamp

发表于 | 阅读数

一颗树 $n$ 个点，$n-1$ 条边，经过每条边都要花费一定的时间，任意两个点都是联通的。

询问经过$k$个点最少需要走多少路程。

设$f[x]$,$x$这个子树的所有关键点到$x$一来一回需要的路程。
$dis[x]$,表示最长的$x$与关键点最长距离。

显然对于根$ans[rt]=dp[rt]-dis[rt]$

考虑如果转移$x\rightarrow to\$

如果$siz[to]=k$
表示不需要做任何处理

但是注意如果$x$子树没有关键点

这个很好理解。

$up[x]$表示外子树最长的$x$与关键点最长距离

更新的时候只要注意下要更新原来$x$子树的最大还是次大值。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<ll, ll>
#define mk make_pair
const ll N = 1e6 + 10;
const ll mod = 1e9 + 7;

ll read()
{
    ll x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

vector<pii> g[N];

pii dis[N];
void cmax(pii &o, ll x)
{
    if (x >= o.first)
    {
        o.second = o.first;
        o.first = x;
    }
    else if (x >= o.second)
    {
        o.second = x;
    }
}
ll f[N];
ll v[N], siz[N];
void dfs(ll x, ll fa)
{
    dis[x] = mk(0, -1e9);
    siz[x] = v[x];
    f[x] = 0;
    for (pii now : g[x])
    {
        ll to = now.first;
        ll w = now.second;
        if (to == fa)
            continue;
        dfs(to, x);
        siz[x] += siz[to];
        if (siz[to])
        {
            f[x] += f[to] + 2 * w;
            cmax(dis[x], dis[to].first + w);
        }
    }
}
ll up[N];
ll k;
void dfs1(ll x, ll fa)
{
  
    for (pii now : g[x])
    {
        ll to = now.first;
        ll w = now.second;
        if (to == fa)
            continue;

        if (siz[to] != k)
        {

            f[to] = f[x];
            if (!siz[to])
                f[to] = f[x] + 2 * w;
            if (dis[x].first == dis[to].first + w )
            {
                up[to] = max(dis[x].second, up[x]) + w;
            }
            else
            {
                up[to] = max(dis[x].first, up[x]) + w;
            }
        }
        dfs1(to, x);
    }
}
int main()
{
    ll n = read();
    k = read();
    for (ll i = 1; i < n; i++)
    {
        ll u = read(), v = read(), w = read();
        g[u].push_back(mk(v, w));
        g[v].push_back(mk(u, w));
    }
    for (ll i = 1; i <= k; i++)
    {
        ll x = read();
        v[x] = 1;
    }
    dfs(1, 0);
    dfs1(1, 0);
    for (ll i = 1; i <= n; i++)
    {
        //cout << f[i] << " " << dis[i].first << endl;
        printf("%lld\n", f[i] - max(up[i], dis[i].first));
    }
}