BZOJ2435 - [Noi2011]道路修建

2017/03/24

我好菜啊 _(:з」∠)_

好水的题啊。

题目描述

给定一棵无根树,设 表示边 两端两个点集的大小, 为边权。

做法

  1. 无根树转有根树
  2. BFS 统计

代码

 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int PSIZ = 2E6 + 1E4;

struct tgno {
    int v, w; tgno *n;
} POOL[PSIZ]; int ppos;
tgno *Head[PSIZ];

inline void _add(int u, int v, int w) {
    POOL[ppos].v = v; POOL[ppos].w = w;
    POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

inline void addEdge(int u, int v, int w) {
    _add(u, v, w), _add(v, u, w);
}

int readint() {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int N;
LL Ans;
LL son[PSIZ];
int que[PSIZ]; int hd, tl;
int fa[PSIZ], val[PSIZ];
LL sz[PSIZ];

void bfs() {
    que[tl++] = 1;
    while(hd != tl) {
        int cur = que[hd]; hd ++;
        for(tgno* i=Head[cur];i;i=i->n) {
            if(i->v != fa[cur]) {
                que[tl++] = i->v;
                fa[i->v] = cur;
                val[i->v] = i->w;
            }
        }
    }

    for(int i=tl-1;i>=0;i--) {
        int cur = que[i];
        sz[cur] ++;
        for(tgno* i=Head[cur];i;i=i->n) {
            if(i->v != fa[cur]) sz[cur] += sz[i->v];
        }
        Ans += LL(val[cur]) * labs((sz[cur]<<1) - N);
    }
}

int main() {
    scanf("%d", &N);

    int u, v, w;
    for(int i=1;i<N;i++) {
        u = readint(); v = readint(); w = readint();
        addEdge(u, v, w);
    }

    bfs();

    printf("%lld\n", Ans);
}