【问题描述】
一个国家有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
记一下取/不取该点的最大值及个数就可以了
按深度从下往上更新
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
// <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; } |
说点什么