题意
不会概括
Solution
对于一个节点(u):
如果(u)是叶子节点，(ans_u=w_u)
如果不是：
假设我们已经知道了(u)所有儿子节点(v_i)的答案，我们需要安排一个合理的顺序，让放梅花过程中的最大值最小。而且由题目性质可知一定是先解决一颗子树，再去解决另一棵。
再假设我们已经定好了顺序，那么过程中的最大值就是之前所有儿子的权值和+当前儿子的答案。节点的答案>=节点的权值，所以这里有一个差量 。
这里的差量=答案-权值。
我们发现如果差量越大，中间过程的浪费就越严重，所以应尽量让差量大的在前，于是贪心策略就出来了。
按儿子节点的差量由大到小排序，扫一遍就可以了(≧▽≦)/啦啦啦
Code
一个错误的写法，挂上引以为戒。
#include<bits/stdc++.h>
#define N (200010)
using namespace std;
struct xbk{int a,b;}now[N],ans[N];
struct edge{int nx,ed;}e[N];
int n,cnt,head[N];
vector<int>v[N];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline bool cmp(xbk aa,xbk bb){return aa.b-aa.a>bb.b-bb.a;}
inline void add(int a,int b){
e[++cnt].ed=b;
e[cnt].nx=head[a];
head[a]=cnt;
}
inline void dfs(int st){
int tot=0;
for(int i=head[st];i;i=e[i].nx){
int ed=e[i].ed;
dfs(ed);
}
if(!(int)v[st].size()){
ans[st].b=ans[st].a;
return;
}
for(int i=0;i<(int)v[st].size();i++) now[++tot]=ans[v[st][i]];
sort(now+1,now+1+tot,cmp);
int nw=0,sum=0;
now[0].a=0,now[0].b=0;
now[tot+1]=now[0];
for(int i=1;i<=tot+1;i++)
nw=max(nw,nw-now[i-1].b+now[i-1].a+now[i].b),sum+=now[i].a;
ans[st].b=max(nw,sum+ans[st].a);
return;
}
int main(){
n=read();
for(int i=2;i<=n;i++){
int u=read();
add(u,i);
v[u].push_back(i);
}
for(int i=1;i<=n;i++) ans[i].a=read();
dfs(1);
for(int i=1;i<=n;i++){
printf("%d ",ans[i].b);
}
puts("");
return 0;
}
正解
#include<bits/stdc++.h>
#define N (100010)
using namespace std;
struct xbk{int a,b;}ans[N];
int n,cnt,head[N];
vector<int>v[N];
inline int read(){
int w=0;
char ch=getchar();
while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9'){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w;
}
inline bool cmp(xbk aa,xbk bb){return aa.b-aa.a>bb.b-bb.a;}
inline void dfs(int st){
int tot=(int)v[st].size();
int nw=0,sum=ans[st].a;
for(int i=0;i<tot;i++) sum+=ans[v[st][i]].a,dfs(v[st][i]);
if(!tot){
ans[st].b=ans[st].a;
return;
}
xbk now[tot+10];
memset(now,0,sizeof(now));
for(int i=0;i<tot;i++) now[i+1]=ans[v[st][i]];
sort(now+1,now+1+tot,cmp);
for(int i=1;i<=tot;i++){
ans[st].b=max(ans[st].b,nw+now[i].b);
nw+=now[i].a;
ans[st].b=max(ans[st].b,sum);
}
return;
}
int main(){
n=read();
for(int i=2;i<=n;i++){
int u=read();
v[u].push_back(i);
}
for(int i=1;i<=n;i++) ans[i].a=read();
dfs(1);
for(int i=1;i<=n;i++)
printf("%d ",ans[i].b);
puts("");
return 0;
}