树形国 – 徐亦轲的博客

【问题描述】

一个国家有n个城市，城市间恰有n-1条道路将城市连接起来，使n个城市构成一棵树。现在需要选取一些城市作为国家直接管理的城市，但这些城市中不能有两个城市有道路直接相连，否则会发生冲突。国王希望选取的城市人口之和要最大，并且想知道有多少种方案可以达到最大人口之和。

【输入格式】

第一行一个数n。
接下来n行，每行两个数f[i]与a[i]，f[i]表示第i个城市的父亲城市，若f[i]为0，则表示该城市为根，a[i]表示该城市的人口数。

【输出格式】

第一行一个数，表示最大的人口和。
第二行一个数，表示方案总数 mod 26457的结果。

【数据范围】

1≤a[i]≤10000
对于20%的数据：n≤20
对于100%的数据：n≤200000

【题解】

裸裸的树形DP

记一下取/不取该点的最大值及个数就可以了

按深度从下往上更新

// <tree.cpp> - 03/05/16 08:05:57
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=200001;
const lol mod=26457;
int f[MAXN],a[MAXN];
lol dp[MAXN][2],ct[MAXN][2];
vector <int> b[MAXN];
queue <int> q;
vector <int> c;
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n=getint(),root;
	for(int i=1;i<=n;i++){
		f[i]=getint();a[i]=getint();
		b[f[i]].push_back(i);
		if(!f[i])root=i;
	}
	q.push(root);
	while(!q.empty()){
		int now=q.front();q.pop();c.push_back(now);
		for(int i=0;i<b[now].size();i++){
			int next=b[now][i];
			if(next!=f[i])q.push(next);
		}
	}
	for(int i=1;i<=n;i++)dp[i][1]=a[i],ct[i][0]=ct[i][1]=1;
	for(int i=c.size()-1;i>=0;i--){
		int now=c[i];
		for(int i=0;i<b[now].size();i++){
			int next=b[now][i];
			dp[now][1]+=dp[next][0];
			ct[now][1]=(ct[now][1]*ct[next][0])%mod;
			dp[now][0]+=max(dp[next][0],dp[next][1]);
			if(dp[next][0]==dp[next][1])ct[now][0]=(ct[now][0]*(ct[next][0]+ct[next][1]))%mod;
			else ct[now][0]=(ct[now][0]*ct[next][dp[next][1]>dp[next][0]])%mod;
		}
	}
	printf("%d\n",max(dp[root][0],dp[root][1]));
	if(dp[root][0]==dp[root][1])printf("%d",(ct[root][0]+ct[root][1])%mod);
	else printf("%d",ct[root][dp[root][1]>dp[root][0]]);
	return 0;
}

// <tree.cpp> - 03/05/16 08:05:57

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=200001;

const lol mod=26457;

int f[MAXN],a[MAXN];

lol dp[MAXN][2],ct[MAXN][2];

vector <int> b[MAXN];

queue <int> q;

vector <int> c;

int main(){

freopen("tree.in","r",stdin);

freopen("tree.out","w",stdout);

int n=getint(),root;

for(int i=1;i<=n;i++){

f[i]=getint();a[i]=getint();

b[f[i]].push_back(i);

if(!f[i])root=i;

}

q.push(root);

while(!q.empty()){

int now=q.front();q.pop();c.push_back(now);

for(int i=0;i<b[now].size();i++){

int next=b[now][i];

if(next!=f[i])q.push(next);

}

for(int i=1;i<=n;i++)dp[i][1]=a[i],ct[i][0]=ct[i][1]=1;

for(int i=c.size()-1;i>=0;i--){

int now=c[i];

for(int i=0;i<b[now].size();i++){

int next=b[now][i];

dp[now][1]+=dp[next][0];

ct[now][1]=(ct[now][1]*ct[next][0])%mod;

dp[now][0]+=max(dp[next][0],dp[next][1]);

if(dp[next][0]==dp[next][1])ct[now][0]=(ct[now][0]*(ct[next][0]+ct[next][1]))%mod;

else ct[now][0]=(ct[now][0]*ct[next][dp[next][1]>dp[next][0]])%mod;

}

printf("%d\n",max(dp[root][0],dp[root][1]));

if(dp[root][0]==dp[root][1])printf("%d",(ct[root][0]+ct[root][1])%mod);

else printf("%d",ct[root][dp[root][1]>dp[root][0]]);

return 0;

}

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【题解】

说点什么