bzoj2435: [Noi2011]道路修建 树上dp

点击打开链接

RE了一辈子...

思路：树上dp，直接dfs找到每个点v的子节点有多少， 那么对答案的贡献是 w*abs((n-size[v])-size[v]);

RE代码：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1100000;vector<pair<ll,ll> > E[maxn<<1];ll size[maxn];ll n,ans;bool vis[maxn];inline ll read(){    ll 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;}void dfs(ll u){	size[u] = 1;	for(int i=0; i<E[u].size(); i++){		int v = E[u][i].first, w = E[u][i].second;		if(!vis[v]){			vis[v] = 1;			dfs(v);			size[u] += size[v];			ans+=(ll)(w*(ll)abs((ll)(size[v]-(n-size[v]))));		}	}}int main(){	n = read();	for(int i=1; i<n; i++){		ll u,v,w; u=read(),v=read(),w=read();		E[u].push_back(make_pair(v,w));		E[v].push_back(make_pair(u,w));	}	vis[n] = 1;	dfs(n);	cout << ans << endl;}