树上 贪心的题目少 自然要记录一番了 最害怕的是dp想不出来方程非得贪心 贪心想不出来策略非得dp。
LINK ： 梅深不见冬 扶苏（指公子扶苏 ，以前最喜欢他了 。 现在不了 懦弱的人 不值得.
题目 意思需要一段时间来理解这里就不再赘述。怎么做？
显然不管对于哪个点都要先做儿子再做父亲，拓扑？可以这样但是树上便利也是可以解决这个问题的。
先dfs儿子 再统计代价 问题的关键是先统计哪个儿子？显然对于每个儿子有两个属性一个是Wx 自己的代价 ANSx子树内的代价 如果想要在这个点放梅花至少需要ANSx个梅花放完之后还剩下 ANSx-Wx个梅花 然后再放下一个 对于下一个 rest是当前还剩的梅花数 那么如果rest<ANSx 那么还需要再拿来ANSx-rest个梅花 然后再在x处放Wx朵梅花。具体就是这样的一个过程 我们发现儿子不同 ANSx和Wx也不同 放哪个儿子的先后顺序就是关键了 爆搜顺序显然不能AC...
具体的 这道题dp很困难 因为我们纠结于这个东西的顺序而并非选取最优的儿子进行转移什么的（虽然实质还是转移但是顺序是关键 制定一个顺序使得答案更优。可以考虑贪心了。考虑使用邻项交换法(微扰法)来观察。
这里进行邻项交换法进行论证。一般都是这个方法吧。
考虑 a和b这两个儿子 的先后对答案的贡献 目标使得f[x]尽可能的小。
先做a再做b ANSa+max(0,ANSb-(ANSa-Wa)) 这里注意其本身的Wx我们不在计入其中因为对于本身和其儿子的顺序就无关了。
先做b再做a ANSb+max(0.ANSa-(ANSb-Wb))
式子列出来了 比下大小吧 （注意在某种前提之下 如Wa>Wb什么的在某种前提下一个式子比另一个式子更优的话我们就得到了策略了。
这里我们就设 Wa>Wb 结果发现没什么用，推不出来什么大小关系 这个时候有两种解决方法：
1 猜下一个结论继续推 2 直接把大小关系列出来 推结论。
显然2 好做 我刚才却一直在做1...没错本人有点蠢...
考虑一式<=二式也就是说先做a再做b比先做b再做a更优。
发现还是不能化简么？其实并非如此...大胆的拆max即可.一式中max拆开 ANSa+0 或 ANSa+ANSb-ANSa+Wa...
发现变成了 max(ANSa,ANSb+Wa);同理二式=max(ANSb,ANSa+Wb);发现还是有max...
再拆分4种情况 ANSa<=ANSb ANSb+Wa<=ANSb ANSa<=ANSa+Wb ANSb+Wa<=ANSa+Wb
这四种情况当中 由于W数组为正数 所以第三个可以忽略 第2个由于我们<=号的强制性 所以这种情况不可能发生。
整理 ANSa<=ANSb ANSb-Wb<=ANSa-Wa 观察第一个式子想要得到ANSa 必然有 ANSa>=ANSb+Wa 可此时ANS<=ANSb但W数组为正数 故此不等式不成立。
所以最终我们得到了一个式子 ANSb-Wb<=ANS-Wa 这个东西具体的当先做a比先做b优的情况下 ANSa-Wa>=ANSb-Wb.
故 利用数学归纳法 可以得出 对于所有儿子按照这个东西排序形成的序列可以使得ANSx达到最优。Wx是自己的 对于每种情况都是相同的处理方式故不在考虑的范围。
code：
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<utility> #include<queue> #include<map> #include<set> #include<bitset> #include<deque> #include<vector> #include<cstdio> #include<cstdlib> #include<iomanip> #include<stack> #include<string> #include<cstring> #define INF 2147483647 #define ll long long #define db double #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define l(p) t[p].l #define r(p) t[p].r #define sum(p) t[p].sum #define mx(p) t[p].mx #define add(p) t[p].add #define tag(p) t[p].tag #define zz p<<1 #define yy p<<1|1 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=100010; int n; int f[MAXN];//f[x]表示 覆盖完x所需最少梅花数 int fa[MAXN],w[MAXN]; vector<int>g[MAXN]; inline int cmp(int x,int y){return f[x]-w[x]>f[y]-w[y];} inline void dp(int x) { int sz=g[x].size(); if(!sz){f[x]=w[x];return;} for(int i=0;i<sz;++i) { int tn=g[x][i]; dp(tn); } sort(g[x].begin(),g[x].end(),cmp); int rest=f[g[x][0]]-w[g[x][0]]; int an=f[g[x][0]]; for(int i=1;i<sz;++i) { int tn=g[x][i]; if(rest<f[tn])an+=f[tn]-rest,rest=f[tn]; rest-=w[tn]; } f[x]=an+max(w[x]-rest,0); } int main() { //freopen("1.in","r",stdin); n=read(); for(int i=1;i<n;++i) { fa[i+1]=read(); g[fa[i+1]].push_back(i+1); } for(int i=1;i<=n;++i)w[i]=read(); dp(1); for(int i=1;i<=n;++i)printf("%d ",f[i]); return 0; }