Solution - P5521 [yLOI2019] 梅深不见冬

Posted on Edited on

链接

题意较清楚，不再赘述。

讲一个比较新奇的做法，不知道对不对，欢迎指正。

拿到题目我猜测父节点和子节点满足某些递推的关系

我们发现完成某一个节点的时候，此时存在权值的节点只有这个节点和它的所有子节点。

然而这不一定是最大值，因为在满足它的子节点的时候，有可能会有超出最终需要值的情况。

但是我们的子节点是逐个满足的，所以每次存在这种超出可能的只有一个子节点。

所以所有可能爆出的情况是：

当前已经满足好的子节点的权值和正在满足的这个子节点满足过程中出现的最大权值和。

不妨用 $ Max[i] $ 来表示满足 $ i $ 节点过程中出现的最大权值和。 $ W[i] $ 表示 $ i $ 的权值。

所以满足子节点的顺序应该是：

按 $ Max[i] - W[i] $ 递减。

$ Code : $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>//
#include<vector>
#include<algorithm>
#define pb push_back
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
using namespace std;
const int N=100005,inf=2e9;
int n,W[N],Ans[N],Max[N];//W[i]权值 Ans[i]答案 Max[i]满足该节点最大权值和（见上文） 
vector<int> Son[N];//Son[i] i的儿子们 
struct node{ int p,tag; };
bool operator < (node a,node b){ return a.p>b.p; }
inline node mp(int x,int y){ node t;t.p=x,t.tag=y;return t; }//结构体：用于排序 
inline int read()//快读 
{
	int num=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch<='9'&&ch>='0') num=(num<<1)+(num<<3)+(ch^48),ch=getchar();
	return num;
}
inline void put(int x){ if (x) put(x/10),putchar(x%10+'0'); }//快输（不会有负数和0） 
int main()
{
	n=read();
	for (int i=2;i<=n;++i) Son[read()].pb(i);
	for (int i=1;i<=n;++i) W[i]=read();//输入 
	for (int i=n;i>=1;--i)
	{
		int sum=0,maxn=0,ansmax=0;
		vector<node> v;//sum子节点权值和  maxn子节点中最大的Max  ansmax子节点中最大的Ans 
		for (int j=0;j<Son[i].size();++j)
		{
			int to=Son[i][j];
			v.pb(mp(Max[to]-W[to],to)),maxn=max(maxn,Max[to]),ansmax=max(ansmax,Ans[to]);
		}//v来存储Max-W并记录属于谁 
		sort(v.begin(),v.end());//排序 
		for (int j=0;j<v.size();++j)
		{
			sum+=W[v[j].tag];//加和
			Ans[i]=max(Ans[i],sum+v[j].p);//sum+v[j].p是因为v[j].p在排序前减掉了W[] 
		}
		Max[i]=max(max(Ans[i],sum+W[i]),maxn);//更新Max 
		Ans[i]=max(Ans[i],max(sum+W[i],ansmax));//更新答案 
	}
	for (int i=1;i<=n;++i) put(Ans[i]),putchar(' ');//输出 
	return 0;
}