51Nod 1405 树的距离之和 (树dp)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1405

中文题面不解释了,两次dfs,第一次自下向上,第二次自上向下。

ans[i]表示i节点的答案,cnt[i]表示i节点为root的子树的节点个数,d[i]表示i节点为root的子树的答案。

 //#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
LL cnt[N], d[N], ans[N], n;
vector <int> edge[N]; void dfs1(int u, int p) {
cnt[u] = ;
d[u] = ;
for(int i = ; i < edge[u].size(); ++i) {
int v = edge[u][i];
if(v == p)
continue;
dfs1(v, u);
cnt[u] += cnt[v];
d[u] += cnt[v] + d[v];
}
} void dfs2(int u, int p) {
if(p != -) {
ans[u] = (ans[p] - d[u] - cnt[u]) + (n - cnt[u]) + d[u];
} else {
ans[u] = d[u];
}
for(int i = ; i < edge[u].size(); ++i) {
int v = edge[u][i];
if(v == p)
continue;
dfs2(v, u);
}
} int main()
{
int u, v;
while(~scanf("%lld", &n)) {
for(int i = ; i <= n; ++i) {
edge[i].clear();
}
for(int i = ; i < n; ++i) {
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(, -);
dfs2(, -);
for(int i = ; i <= n; ++i) {
printf("%lld\n", ans[i]);
}
}
return ;
}
上一篇:IOS 面试 --- 网络部分


下一篇:清除SQL Server 2008中登陆时的历史记录