Fork me on GitHub

「NOI2011」道路修建 树形dp

发表于 | 分类于
字数统计: 486字 | 阅读时长 ≈ 3分钟

Links there:NOI2011道路修建

题意

给出一个树,定义每条边的建造费用为边两侧点的差的绝对值于边权$w_i$的乘积,求出总的建造费用.

(诶是不是太简洁了)

思路

直接树形dp就行啦.似乎没什么可以思考的地方呢…

Code

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
//my vegetable has exploded. :(
#include<bits/stdc++.h>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define MM(x,y) memset(x,y,sizeof(x))
#define MCPY(a,b) memcpy(a,b,sizeof(b))
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define fi first
#define se second
#define int long long
using namespace std;

inline int quickpow(int m,int n,int p){int b=1;while(n){if(n&1)b=b*m%p;n=n>>1;m=m*m%p;}return b;}
inline int getinv(int x,int p){return quickpow(x,p-2,p);}
inline int read(void){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x * f;
}

///------------------head------------------
const int MAXN = 1e6+100;
int sz[MAXN],n,vis[MAXN];
struct Edges{
	int to,w,nxt;
}E[MAXN<<1];
int head[MAXN],cnt=0,ans=0;
inline void addedge(int u,int v,int w){
	E[++cnt].nxt = head[u];E[cnt].to = v;E[cnt].w = w;head[u] = cnt;
	E[++cnt].nxt = head[v];E[cnt].to = u;E[cnt].w = w;head[v] = cnt;
}
void dfs(int cur){
	sz[cur] = 1;
	for (int i = head[cur]; i; i = E[i].nxt) {
		int v = E[i].to,w = E[i].w;
		if (!vis[v]) {
			vis[v] = 1;
			dfs(v);
			sz[cur] += sz[v];
			ans += w * abs(n-(sz[v]) - sz[v]);
		}
	}
}
signed main(signed argc, char *argv[]){
	n=read();
	MM(head,0); MM(vis,0);
	rep(i,1,n-1) {int u=read(),v=read(),w=read(); addedge(u,v,w);}
	vis[1]=1;
	dfs(1);
	printf("%lld\n",ans);
	return 0;
}

/* Examples: */
/*
6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1
*/

/*
20
*/