首页 > 代码库 > POI 2014 HOTELS (树形DP)
POI 2014 HOTELS (树形DP)
题目链接 HOTELS
依次枚举每个点,以该点为中心扩展。
每次枚举的时候,从该点的儿子依次出发,搜完一个儿子所有的点之后进行答案统计。
这里用了一个小trick。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for(int i(a); i <= (b); ++i) 6 #define for_edge(i, x) for(int i = H[x]; i; i = X[i]) 7 8 int n, x, y, et = 0; 9 int E[100010], X[100010], H[100010], f[5010], g[5010], tmp[5010]; 10 long long ans; 11 12 inline void addedge(int a, int b){ 13 E[++et] = b, X[et] = H[a], H[a] = et; 14 E[++et] = a, X[et] = H[b], H[b] = et; 15 } 16 17 void dfs(int x, int fa, int dep){ 18 ++tmp[dep]; 19 for_edge(i, x){ 20 int u = E[i]; 21 if (u != fa) dfs(u, x, dep + 1); 22 } 23 } 24 25 int main(){ 26 27 scanf("%d", &n); 28 rep(i, 1, n - 1){ 29 scanf("%d%d", &x, &y); 30 addedge(x, y); 31 } 32 33 rep(u, 1, n){ 34 memset(f, 0, sizeof f); 35 memset(g, 0, sizeof g); 36 for_edge(i, u){ 37 memset(tmp, 0, sizeof tmp); 38 x = E[i]; 39 dfs(x, u, 1); 40 rep(j, 1, n){ 41 ans += (long long)g[j] * tmp[j]; 42 g[j] += f[j] * tmp[j]; 43 f[j] += tmp[j]; 44 } 45 } 46 } 47 48 printf("%lld\n", ans); 49 return 0; 50 51 }
POI 2014 HOTELS (树形DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。