题目描述
某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
输入输出格式
输入格式：
第一行一个整数N。(1<=N<=6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0 0
输出格式：
输出最大的快乐指数。
输入输出样例
输入样例#1： 复制
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
输出样例#1：
View Code
View Code
View Code
5
入门树形dp
一开始90分 少考虑了一种情况
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=6000+5; const int M=50005; int head[M],pos; struct Edge { int nex,to,v; }edge[M]; void add(int a,int b) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].to=b; } int n,m; int dp[N][N]; int siz[N]; int node[N]; int vis[N]; void dfs(int u,int fa) { for(int i=head[u];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dfs(v,u); dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]); dp[u][0]=max(dp[u][0],dp[u][0]+dp[v][1]); } } int main() { RI(n); rep(i,1,n) RI(node[i]),dp[i][1]=node[i]; int a,b; while(RII(a,b)) { if(a==0&&b==0)break; add(a,b);add(b,a); vis[a]=1; } int root; rep(i,1,n) if(!vis[i])root=i; dfs(root,0); cout<<max( dp[root][0],dp[root][1] ); return 0; }
修改后：
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=6000+5; const int M=50005; int head[M],pos; struct Edge { int nex,to,v; }edge[M]; void add(int a,int b) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].to=b; } int n,m; int dp[N][N]; int siz[N]; int node[N]; int vis[N]; void dfs(int u,int fa) { for(int i=head[u];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dfs(v,u); dp[u][1]=max(dp[u][1],dp[u][1]+dp[v][0]); dp[u][0]=max(dp[u][0],max(dp[v][0]+dp[u][0],dp[v][1]+dp[u][0]) ); } } int main() { RI(n); rep(i,1,n) { RI(node[i]); if(node[i]>0)dp[i][1]=node[i]; } int a,b; while(RII(a,b)) { if(a==0&&b==0)break; add(a,b);add(b,a); vis[a]=1; } int root; rep(i,1,n) if(!vis[i])root=i; dfs(root,0); cout<<max( dp[root][0],dp[root][1] ); return 0; }
大佬的做法：
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=6000+5; const int M=50005; int head[M],pos; struct Edge { int nex,to,v; }edge[M]; void add(int a,int b) { edge[++pos].nex=head[a]; head[a]=pos; edge[pos].to=b; } int n,m; int dp[N][2]; int node[N]; int vis[N]; void dfs(int u,int fa) { for(int i=head[u];i;i=edge[i].nex) { int v=edge[i].to; if(v==fa)continue; dfs(v,u); dp[u][0]+=max( dp[v][1],dp[v][0] ); dp[u][1]+=dp[v][0]; } } int main() { RI(n); rep(i,1,n) { RI(node[i]); dp[i][1]=node[i]; } int a,b; while(RII(a,b)) { if(a==0&&b==0)break; add(a,b);add(b,a); vis[a]=1; } int root; rep(i,1,n) if(!vis[i])root=i; dfs(root,0); cout<<max( dp[root][0],dp[root][1] ); return 0; }