题意,,,这是车上每次只能拉一个人回去的代码。
查看原帖
题意,,,这是车上每次只能拉一个人回去的代码。
524191
Man_CCNU楼主2023/6/9 10:30
#include<iostream>

using namespace std;

const int N = 5e5 + 10, M = 1e6 + 10;

int f[N], g[N], h[N], e[M], ne[M], w[M], sz[N], d1[N],d2[N], df[N],d2f[N], n,m, idx = 1;
bool ff[N];

void connec(int x, int y, int z)
{
    e[idx] = y;
    w[idx] = z;
    ne[idx] = h[x];
    h[x] = idx;
    idx++;
}
void dfs(int x, int fa)
{
    sz[x] = ff[x];
    if (ff[x]) {
        d1[x] = 0;
        d2[x] = -1;
    }
    else {
        d1[x] = -1;
        d2[x] = -1;
    }
    for (int i = h[x]; i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {
            dfs(j, x);
            sz[x] += sz[j];
            g[x] = g[x] + g[j] + sz[j]*2* w[i];
            if (d1[j]>=0) {
                if (d1[j] + w[i] > d1[x]) {
                    d2[x] = d1[x];
                    d1[x] = d1[j] + w[i];
                    d2f[x] = df[x];
                    df[x] = j;
                }
                else {
                    if (d1[j] + w[i] > d2[x]) {
                        d2[x] = d1[j] + w[i];
                        d2f[x] = j;
                    }
                }
                
            }
        }
    }
}
void dfs2(int x, int fa)
{
    for (int i = h[x]; i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {
            if (j == 5) {
                int xxx = 0;
            }
            if (df[x] != j && d2f[x] != j) {
                if (d1[x] + w[i] >= d1[j]) {
                    d2f[j] = df[j];
                    d2[j] = d1[j];
                    if (d2[x] + w[i] > d2[j]) d2[j] = d2[x] + w[i], d2f[j] = x;
                    df[j] = x;
                    d1[j] = d1[x] + w[i];
                }
            }
            else if (df[x] == j && d2f[x] != j) {
                if (d2[x] + w[i] >= d1[j]) {
                    d2f[j] = df[j];
                    d2[j] = d1[j];
                    if (d1[x] - w[i] > d2[j]) d2[j] = d1[x] - w[i], d2f[j] = x;
                    df[j] = x;
                    d1[j] = d2[x] + w[i];
                }
            }
            else if (df[x] != j && d2f[x] == j) {
                if (d1[x] + w[i] >= d1[j]) {
                    d2f[j] = df[j];
                    d2[j] = d1[j];
                    if (d2[x] - w[i] > d2[j]) d2[j] = d2[x] - w[i], d2f[j] = x;
                    df[j] = x;
                    d1[j] = d1[x] + w[i]; 
                }

            }
            else {
                if (d1[x] - w[i] > d1[j]) {
                    d2[j] = d1[j];
                    d2f[j] = df[j];
                    if (d2[x] - w[i] > d2[j]) d2f[j] = x, d2[j] = d2[x] - w[i];
                    df[j] = x;
                    d1[j] = d1[x] - w[i];
                }
            }
            f[j] = f[x] - g[j] - sz[j] * 2 * w[i] + g[j] + (m - sz[j]) * 2*w[i];
            dfs2(j, x);
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        connec(x, y, z);
        connec(y, x, z);
    }
    for (int i = 1; i <= m; i++) {
        int tem;
        cin >> tem;
        ff[tem] = 1;
    }
    dfs(1, 0);
    f[1] = g[1];
    dfs2(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << f[i] - d1[i] << endl;
    }

    return 0;
}
2023/6/9 10:30
加载中...