bzoj3743 [Coci2015]Kamp 常州模拟赛d6t2

3743: [Coci2015]Kamp

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 484  Solved: 229
[Submit][Status][Discuss]

Description

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

有K个人（分布在K个不同的点）要集中到一个点举行聚会。

聚会结束后需要一辆车从举行聚会的这点出发，把这K个人分别送回去。

请你回答，对于i=1~n，如果在第i个点举行聚会，司机最少需要多少时间把K个人都送回家。

Input

第一行两个数，n，K。

接下来n-1行，每行三个数，x，y，z表示x到y之间有一条需要花费z时间的边。

接下来K行，每行一个数，表示K个人的分布。

Output

输出n个数，第i行的数表示：如果在第i个点举行聚会，司机需要的最少时间。

Sample Input

7 2
1 2 4
1 3 1
2 5 1
2 4 2
4 7 3
4 6 2
3
7

Sample Output

11
15
10
13
16
15
10

HINT

【数据规模】

K <= N <= 500000

1 <= x,y <= N, 1 <= z <= 1000000

分析：本来想用状压dp的，但是n这么大，怎么压的下来。其实这道题有一个结论：如果我们把要送达的点建立一棵树，那么答案就是这棵树上的边权和*2+i到这棵树的最短距离(假设为j点)-j到树上最远一点的距离.其实也很好想为什么，要遍历树上的点最少肯定要每条边都走两次，i点要到这棵树上肯定要走最短距离，我们到一个点后就不回起点了，那么肯定终点在最远的那个点上.

      那么想要做出这道题就要用到4个dfs.首先求出每个点在不在树上,然后求出i到树上最近的点和最短距离，接下来求出每个点到它的叶子节点的最长距离和次长距离，最后求出每个点的最长距离.

      第一步和第二步很好理解，关键是最后两步，我们求最长距离为什么还要求每个点到它的叶子节点的最长距离和次长距离呢？其实这有点像树链剖分，我们把树链分为最长链和次长链，位于最长链的儿子成为重儿子，重儿子的最远距离点肯定在它的子节点中或者次长链中，这就包含了最长链和次长链两种情况，没有其它情况了，轻儿子的最远距离也肯定在它的子节点或者最长链中，所以我们先求出父节点到子节点的最远距离和次远距离，然后利用父节点更新子节点，很难想到啊.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 500010;

int n, k,head[maxn],to[maxn * 2],nextt[maxn * 2],w[maxn * 2],tot = 1,ner[maxn],son[maxn];
long long mind[maxn],maxd[maxn],secd[maxn],d[maxn],sum;
bool flag[maxn],vis[maxn];

void add(int x, int y, int z)
{
    w[tot] = z;
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

bool dfs1(int x)   //找树
{
    vis[x] = 1;
    for (int i = head[x]; i; i = nextt[i])
    {
        int v = to[i];
        if (!vis[v])
        {
            if (dfs1(v))
            {
                flag[x] = 1;
                sum += w[i];
            }
        }
    }
    return flag[x];
}

void dfs2(int x)  //找最短距离
{
    vis[x] = 1;
    if (flag[x])
        ner[x] = x;
    for (int i = head[x]; i; i = nextt[i])
    {
        int v = to[i];
        if (!vis[v] && !flag[v])
        {
            mind[v] = mind[x] + w[i];
            ner[v] = ner[x];
        }
        if (!vis[v])
            dfs2(v);
    }
}

long long dfs3(int x)  //最长距离+次长距离
{
    vis[x] = 1;
    for (int i = head[x]; i; i = nextt[i])
    {
        int v = to[i];
        if (!vis[v] && flag[v])
        {
            long long t = dfs3(v) + w[i];
            if (t > maxd[x])
            {
                secd[x] = maxd[x];
                maxd[x] = t;
                son[x] = v;
            }
            else
                if (t > secd[x])
                    secd[x] = t;
        }
    }
    return maxd[x];
}

void dfs4(int x, long long lmax)   //最后的更新
{
    vis[x] = 1;
    for (int i = head[x]; i; i = nextt[i])
    {
        int v = to[i];
        d[x] = max(lmax, maxd[x]);
        if (flag[v] && !vis[v])
        {
            if (v == son[x])
                dfs4(v, max(lmax, secd[x]) + w[i]);
            else
                dfs4(v, max(lmax, maxd[x]) + w[i]);
        }
    }
}

int main()
{
    memset(flag, false, sizeof(flag));
    scanf("%d%d", &n, &k); 
    for (int i = 1; i < n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    int t;
    for (int i = 1; i <= k; i++)
    {
        scanf("%d", &t);
        flag[t] = 1;
    }
    dfs1(t);
    memset(vis, 0, sizeof(vis));
    dfs2(t);
    memset(vis, 0, sizeof(vis));
    dfs3(t);
    memset(vis, 0, sizeof(vis));
    dfs4(t, 0);
    for (int i = 1; i <= n; i++)
        printf("%lld
", sum * 2 + mind[i] - d[ner[i]]);

    return 0;
}