题目描述
SUPER M是一个很经典的游戏
现在改一下规则
有N个城堡（0到n-1）
每个城堡都有一个KOOPA，注意：有些KOOPA会可能有1个FATHER-KOOPA
公主在最后一个城堡内（N-1）
现在每次只能打一个城堡且必须在T[I]时间内打完（否则游戏结束）
如果（N-1）号城堡打完
游戏结束
如果一个KOOPA至少有2个SON-KOOPA被打败
则必须马上去击败这个KOOPA否则会因为愤怒而做掉公主
现在求
最长游戏时间
题解
考虑游戏结束是什么情况：
n
−
1
n-1
n−1的一个儿子全部打死，其他儿子除了根都尽量打了，一个儿子打到根的一刻就结束了。那么我们通过观察可以发现有两个状态需要除了：
f
[
x
]
f[x]
f[x]表示这个子树打到根节点就不打了的最大值
g
[
x
]
g[x]
g[x]表示这个子树不打根节点能打到的最大值 显然
g
[
x
]
g[x]
g[x]也很好转移，一个子树全打死，其他都是
g
[
]
g[\ ]
g[ ]
f
[
x
]
f[x]
f[x]就是一个子树全打死一个是
f
[
]
f[\ ]
f[ ]其他是
g
[
]
g[\ ]
g[ ] 注意
f
[
x
]
f[x]
f[x]的两个最大是同一个的情况，要同时存
f
[
x
]
f[x]
f[x]和
s
u
m
[
x
]
sum[x]
sum[x]的最大值和次大值
代码
#include<bits/stdc++.h>
#define maxn 100005
#define MAXN 1000005
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
LL read(){
LL res,f=1; char c;
while(!isdigit(c=getchar())) if(c=='-') f=-1; res=(c^48);
while(isdigit(c=getchar())) res=(res<<3)+(res<<1)+(c^48);
return res*f;
}
struct EDGE{
int u,v,nxt;
}e[maxn<<1];
int T,n,cnt,head[maxn],f[maxn],g[maxn],sum[maxn],w[maxn];
void add(int u,int v){
e[++cnt]=(EDGE){u,v,head[u]};
head[u]=cnt;
}
void DFS(int u){
int M=0,M1=0,M2=0,m1=0,m2=0;
sum[u]+=w[u];
f[u]+=w[u];
for(int i=head[u];~i;i=e[i].nxt){
int v=e[i].v;
DFS(v);
sum[u]+=sum[v];
g[u]+=g[v];
f[u]+=g[v];
M=max(M,sum[v]-g[v]);
if(f[v]-g[v]>f[M1]-g[M1] || !M1){
M2=M1;
M1=v;
}
else if(f[v]-g[v]>f[M2]-g[M2] || !M2){
M2=v;
}
if(sum[v]-g[v]>sum[m1]-g[m1] || !m1){
m2=m1;
m1=v;
}
else if(sum[v]-g[v]>sum[m2]-g[m2] || !m2){
m2=v;
}
}
g[u]+=M;
if(M1!=m1){
f[u]+=f[M1]-g[M1];
f[u]+=sum[m1]-g[m1];
}
else f[u]+=max(f[M1]-g[M1]+sum[m2]-g[m2],f[M2]-g[M2]+sum[m1]-g[m1]);
}
int main(){
while(n=read()){
for(int i=1;i<=n;i++){
w[i]=read();
}
cnt=0;
memset(head,-1,sizeof head);
memset(f,0,sizeof f);
memset(g,0,sizeof g);
memset(sum,0,sizeof sum);
for(int i=1;i<=n;i++){
int fa=read();
if(~fa){add(fa+1,i);}
}
DFS(n);
for(int i=1;i<=n;i++){
if(!sum[i]) f[n]+=w[i];
}
printf("%d\n",f[n]);
}
return 0;
}
