FZU2038 Another Postman Problem 树状DP

题目比较难看懂，给了n个点和n-1条边，并且保证所有的点都是连通的，求每个点到其他点的距离的和，每枚举一个点去走肯定是比较麻烦的，可以转化成求每条边走的次数，那么答案就是 次数乘以边权，每条边走的次数 等于 整个树的 节点数 减去当前子树的节点数 然后再乘以当前的节点数，可能有点绕口，画个树 推一下，求出以后呢 再乘以边权 就是最后的答案了，

我用了两边的搜索，第一遍求出走的时候当前一步的子树的节点数，保存在DP数组里面，然后第二遍搜索的时候再进行计算，其实只需要一次搜索就可以了，第一遍搜索搜完以后马上递归回去即可

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

struct Node {
	int value;
	int nex;
	int from,to;
}edge[1000000 + 5];

ll head[100000 + 5];
bool vis[100000 + 5];
ll dp[1000000 + 5];

ll n;
ll ans;
int tot;

void clear() {
	memset(edge,0,sizeof(edge));
	memset(head,-1,sizeof(head));
	memset(vis,false,sizeof(vis));
	memset(dp,0,sizeof(dp));
	tot = 0;
	ans = 0;
}

void add(int u,int v,int w) {
	edge[tot].from = u;
	edge[tot].to = v;
	edge[tot].value = w;
	edge[tot].nex = head[u];
	head[u] = tot++;
}

void dfs(int u,int e) {
	vis[u] = true;
	dp[u] = 1;
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		int v = edge[i].to;
		if(v == e)
			continue;
		if(!vis[v]) {
			dfs(v,u);
			dp[u] += dp[v];
		}
	}
}

void cal(int u,int e) {
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		int v = edge[i].to;
		if(v == e)
			continue;
		ans += edge[i].value*(n-dp[v]) * dp[v];
		cal(v,u);
	}
}

int main() {
	int t;
	int Case = 0;
	scanf("%d",&t);
	while(t--) {
		clear();
		scanf("%I64d",&n);
		int tmpn = n;
		tmpn--;
		while(tmpn--) {
			ll u,v,w;
			scanf("%I64d %I64d %I64d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		dfs(0,-1);
		cal(0,-1);
		printf("Case %d: %I64d\n",++Case,ans * 2);
	}
	return EXIT_SUCCESS;
}

FZU2038 Another Postman Problem 树状DP,布布扣,bubuko.com

FZU2038 Another Postman Problem 树状DP

原文：http://blog.csdn.net/yitiaodacaidog/article/details/20229765