QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#326#86781#4406. 独立集问题CrysflyCrysflySuccess!2023-03-10 21:57:122023-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. 独立集问题Crysfly97 153ms115264kbC++141.6kb2023-03-10 21:42:362023-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;
}