QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #326 | #86781 | #4406. 独立集问题 | Crysfly | Crysfly | Success! | 2023-03-10 21:57:12 | 2023-03-10 21:57:15 |
詳細信息
Extra Test:
Time Limit Exceeded
input:
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
result:
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #86781 | #4406. 独立集问题 | Crysfly | 97 | 153ms | 115264kb | C++14 | 1.6kb | 2023-03-10 21:42:36 | 2023-03-10 22:03:07 |
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f
int n,fa[maxn],w[maxn][2];
vi e[maxn];
int f[maxn][2],g[maxn][2][2],mxg[maxn],mx[2];
void dfs(int u)
{
for(int v:e[u])dfs(v);
For(i,0,1)f[u][i]=w[u][i];
mx[0]=mx[1]=0;
for(int v:e[u])
For(i,0,1)mx[i]+=max(f[v][i],mxg[v]);
For(i,0,1)f[u][i]+=max(mx[0],mx[1]);
For(i,0,1)g[u][i][1]=w[u][!i];
mx[0]=mx[1]=0;
for(int v:e[u])
For(i,0,1)mx[i]+=max(f[v][i],max(g[v][0][0],g[v][1][0]));
For(i,0,1)g[u][i][1]+=mx[i];
For(i,0,1){
g[u][i][0]=-inf;
for(int v:e[u]){
For(c,0,1){
int now=w[u][c]+max(g[v][c][0],g[v][c][1]);
for(int w:e[u])
if(w!=v) now+=max(f[w][i],mxg[w]);
g[u][i][0]=max(g[u][i][0],now);
}
}
}
mxg[u]=-inf;
For(i,0,1)For(j,0,1)mxg[u]=max(mxg[u],g[u][i][j]);
// cout<<"f: "<<u<<"\n";
// For(i,0,1)cout<<f[u][i]<<" ";puts("");
// For(i,0,1)For(j,0,1)cout<<g[u][i][j]<<" \n"[j==1];
}
signed main()
{
n=read();
memset(f,-63,sizeof f);
For(i,1,n)w[i][0]=read(),w[i][1]=-w[i][0];
For(i,2,n)fa[i]=read(),e[fa[i]].pb(i);
dfs(1);
cout<<mxg[1];
return 0;
}