CF533B Work Group

Jisoo

不显然的树上dp

定义\(f_{i,j}\)为第i位和为子树所选奇数个/偶数个点的方案数

然后显然会发现奇数加奇数等于偶数等规律

然后就可以转移了

#include<cstdio>#include<iostream>#include<cstring>#include<iomanip>#include<cmath>#include<algorithm>#define int long longusing namespace std;template<class T>inline void read(T &x){    x=0;register char c=getchar();register bool f=0;    while(!isdigit(c))f^=c=='-',c=getchar();    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();    if(f)x=-x;}template<class T>inline void print(T x){    if(x<0)putchar('-'),x=-x;    if(x>9)print(x/10);    putchar('0'+x%10);}int f[2000005][2];int n;struct e{	int to;	int ne;}ed[200001];int a[2000005];int head[2000005];int x,y;int p;void add(int f,int to){	p++;	ed[p].ne=head[f];	ed[p].to=to;	head[f]=p;}void dfs(int ro){	f[ro][1]=-999999999;	for(int i=head[ro];i;i=ed[i].ne){		int v=ed[i].to;		//if(v==fa) continue;		dfs(v);		int x=f[ro][0],y=f[ro][1];		f[ro][0]=max(x+f[v][0],y+f[v][1]);		f[ro][1]=max(x+f[v][1],y+f[v][0]);	}	f[ro][1]=max(f[ro][1],f[ro][0]+a[ro]);}signed main(){	ios::sync_with_stdio(false);	read(n);	for(int i=1;i<=n;++i){		read(x);		read(a[i]);		if(x!=-1) 		add(x,i);	}	//memset(f,0xc0,sizeof(f));	dfs(1);		cout<<max(f[1][0],f[1][1]);    return 0;}