[NOI2011]道路修建 Bzoj2435

题目的意思就是给定一张有根图,根据所给规则计算费用之和。这题有点像bzoj1131,但更简单,因为不用换根。

我们可以假定以1为根,计算出以i为根节点的子树的节点数son[i]。统计时对于边(u,v),假设u为以1为根的树中v的父亲(反过来也一样),那么费用就要加上son[v]+(n-son[v])。
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
/**************************************************************
    Problem: 2435
    User: abcdabcd987
    Language: C++
    Result: Accepted
    Time:6944 ms
    Memory:49116 kb
****************************************************************/

#include <cstdlib>
#include <iostream>
using namespace std;

struct link {
  int v,next;
} g[3000000];
int q[1000001],son[1000001],father[1000001],n,top,root,a[1000000][3];
bool s[1000001];
long long ans;
inline void join(const int x,const int y) {
  g[++top].v=y;
  g[top].next=g[x].next;
  g[x].next=top;
}
void bfs(const int source) {
  int head=0,tail=1;
  q[tail]=source;
  s[source]=true;
  father[source]=-1;
  while (head<tail) {
    int u=q[++head],v=g[u].next;
    son[u]=1;
    while (v!=-1) {
      if (!s[g[v].v]) {
        s[g[v].v]=true;
        father[g[v].v]=u;
        q[++tail]=g[v].v;
      }
      v=g[v].next;
    }
  }
  for (int i=n;i>1;--i) son[father[q[i]]]+=son[q[i]];
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n;
  for (int i=1;i<=n;++i) g[i].next=-1;
  top=n;
  for (int i=1;i<n;++i) {
    cin>>a[i][0]>>a[i][1]>>a[i][2];
    join(a[i][0],a[i][1]);
    join(a[i][1],a[i][0]);
  }
  bfs(1);
  for (int i=1;i<n;++i) {
    int k=father[a[i][0]]==a[i][1]?a[i][0]:a[i][1];
    ans+=static_cast<long long>(abs(son[k]-(n-son[k])))*a[i][2];
  }
  cout<<ans;
}

Comments