树型dp hdu5834 Magic boy Bi Luo with his excited tree
传送门:点击打开连接
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]";
#define FIN freopen("input.txt","r",stdin);
#define FOUT freopen("output.txt","w+",stdout);
//#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int Head[MX],erear;
struct Edge {
int v,cost,nxt;
} E[MX * 2];
void edge_init() {
erear = 0;
memset(Head,-1,sizeof(Head));
}
void edge_add(int u,int v,int cost) {
E[erear].v = v;
E[erear].cost = cost;
E[erear].nxt = Head[u];
Head[u] = erear++;
}
int ans[MX];
int W[MX],A[MX],B[MX],C[MX],D[MX];
int get_child(int u,int f,vector<int> &ch) {
int tot = 0;
for(int i = Head[u]; ~i; i = E[i].nxt) {
int v = E[i].v;
if(v == f) continue;
tot++;
}
ch.resize(tot + 1); tot = 0;
for(int i = Head[u]; ~i; i = E[i].nxt) {
int v = E[i].v;
if(v == f) continue;
ch[++tot] = i;
}
return tot;
}
inline int func(int x) {
return max(x,0);
}
void DFS1(int u,int f) {
vector<int> ch,suf;
int tot = get_child(u,f,ch);
suf.resize(tot + 2);
A[u] = B[u] = 0;
suf[tot + 1] = 0;
for(int i = tot; i >= 1; i--) {
int v = E[ch[i]].v,cost = E[ch[i]].cost;
DFS1(v,u);
suf[i] = suf[i + 1] + func(A[v] + W[v] - 2 * cost);
}
A[u] = suf[1];
int pre = 0;
for(int i = 1; i <= tot; i++) {
int v = E[ch[i]].v,cost = E[ch[i]].cost;
B[u] = max(B[u],pre + suf[i + 1] + func(B[v] + W[v] - cost));
pre += func(A[v] + W[v] - 2 * cost);
}
}
void DFS2(int u,int f) {
ans[u] = max(A[u] + D[u],B[u] + C[u]) + W[u];
vector<int> ch,suf,suf2;
int tot = get_child(u,ch);
suf.resize(tot + 2);
suf2.resize(tot + 2);
suf[tot + 1] = suf2[tot + 1] = 0;
for(int i = tot; i >= 1; i--) {
int v = E[ch[i]].v,cost = E[ch[i]].cost;
suf[i] = suf[i + 1] + func(A[v] + W[v] - 2 * cost);
suf2[i] = max(suf2[i + 1],func(B[v] + W[v] - cost) - func(A[v] + W[v] - 2 * cost));
}
int pre = 0,pre2 = 0;
for(int i = 1; i <= tot; i++) {
int v = E[ch[i]].v,cost = E[ch[i]].cost;
C[v] = func(pre + suf[i + 1] + C[u] + W[u] - 2 * cost);
D[v] = func(pre + suf[i + 1] + C[u] + W[u] + max(pre2,suf2[i + 1]) - cost);
D[v] = max(D[v],func(pre + suf[i + 1] + D[u] + W[u] - cost));
pre += func(A[v] + W[v] - 2 * cost);
pre2 = max(pre2,func(B[v] + W[v] - cost) - func(A[v] + W[v] - 2 * cost));
DFS2(v,u);
}
}
int main() {
//FIN;
int T,n,ansk = 0;
scanf("%d",&T);
while(T--) {
printf("Case #%d:n",++ansk);
edge_init();
scanf("%d",&n);
for(int i = 1; i <= n; i++) scanf("%d",&W[i]);
for(int i = 1; i <= n - 1; i++) {
int u,v,cost;
scanf("%d%d%d",&u,&v,&cost);
edge_add(u,cost);
edge_add(v,u,cost);
}
DFS1(1,-1);
C[1] = D[1] = 0;
DFS2(1,-1);
for(int i = 1; i <= n; i++) {
printf("%dn",ans[i]);
// printf("%d,%d,%dn",A[i],B[i],C[i],D[i]);
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |