HDU 5834 Magic boy Bi Luo with his excited tree——树形dp

HDU 5834 Magic boy Bi Luo with his excited tree——树形dp

唯一要注意的就是最大和次大，他们可以在一条树链上，值可以相同

PS：超时超到怀疑人生，最后发现数组开大了

#include #include #include #include using namespace std;const int maxn = 1e5 + 10;inline int read() { int s = 0; char ch = getchar(); for(; ch < '0' || ch > '9'; ch = getchar()); for(; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0'; return s;}int T, n, tot, head[maxn], val[maxn], id[maxn], son[maxn][3], ans[maxn];struct Edge { int to, cost, next;}edge[maxn<<1];inline void init() { tot = 0; memset(head, -1, sizeof(head));}inline void addedge(int u, int v, int cost) { ++tot; edge[tot].to = v, edge[tot].cost = cost, edge[tot].next = head[u]; head[u] = tot;}void dfs1(int u, int p) { for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p) continue; dfs1(v, u); son[u][0] += max(0, son[v][0] - 2 * cost); } for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p) continue; int temp = son[u][0] - max(0, son[v][0] - 2 * cost) + max(0, son[v][1] - cost); if (son[u][1] <= temp) { son[u][2] = son[u][1]; son[u][1] = temp; id[u] = v; } else if (son[u][2] < temp) son[u][2] = temp; }}void dfs2(int u, int p, int x, int y) { ans[u] = max(son[u][1] + x, son[u][0] + y); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to, cost = edge[i].cost; if (v == p) continue; int t0 = son[u][0] - max(0, son[v][0] - 2 * cost); int xx = max(0, x + t0 - 2 * cost); int t1; if (v == id[u]) t1 = son[u][2] - max(0, son[v][0] - 2 * cost); else t1 = son[u][1] - max(0, son[v][0] - 2 * cost); int yy = max(0, max(x + t1, y + t0) - cost); dfs2(v, u, xx, yy); }}int main() { T = read(); for (int kase = 1; kase <= T; kase++) { n = read(); init(); int u, v, cost; for (int i = 1; i <= n; i++) scanf("%d", &val[i]); for (int i = 1; i <= n - 1; i++) { u = read(); v = read(), cost = read(); addedge(u, v, cost); addedge(v, u, cost); } memset(id, -1, sizeof(id)); for (int i = 1; i <= n; i++) { son[i][0] = son[i][1] = son[i][2] = val[i]; } dfs1(1, -1); dfs2(1, -1, 0, 0); printf("Case #%d:\n", kase); for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。