每日刷题（8）

阅读数: 次 2021-03-20

1. Database

1.1. 题目

链接：https://ac.nowcoder.com/acm/contest/11168/C
来源：牛客网

题目描述
给定一棵 n 个点的带点权的有根树，根节点为 1 。
要选出两个节点，满足任意一个不是另一个的祖先节点，最大化以两个节点为根的子树的点权和。
如果选不出两棵合法的子树，则输出“Error”。
输入描述:
第一行一个正整数 n 。
第二行 n 个整数，分别表示 n 个点的点权。
接下来 n - 1 行，每行两个正整数 u，v 表示 u 和 v 之间有一条连边。
输出描述:
一个整数，表示最大的点权和

1.2. 样例输入&&样例输出

样例

5
10 -5 5 6 7
1 2
1 3
2 4
2 5

1.3. 思路

这题的题目的意思是要你找出两个父节点不一样的两个节点，使得他们的子树权和最大
这里使用dfs递归从底往上更新mx数组，mx数组的意思是mx以下的后代节点的点权和
而sum数组的意思是以u为根节点的子树权和
使用邻接表储存树即可
我们找出最大的和次大的即可

1.4. AC代码

#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
#include<list>
#include<map>
#include<cstdio>
typedef long long ll;
typedef int64_t s64;
using namespace std;
const int maxn = 1e6;
ll m, n, minlen, len, cnt = 0, q,k,h;
const int MOD= 1e9 + 7;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define pre(i,r,l) for(int i=r;i>=l;i--)
const int INF=1e18;
int tot;
map<string,ll>mp;
vector<int>son[maxn];
ll w[maxn],mx[maxn],sum[maxn];
ll ans=-INF;
void dfs(int u,int fa){
    ll maxnum=-INF;sum[u]=w[u];
    for(int i=0;i<son[u].size();i++){
        int v=son[u][i];
        if(v==fa)continue;
        dfs(v,u);sum[u]+=sum[v];
        if(maxnum!=-INF)ans=max(ans,maxnum+mx[v]);
        maxnum=max(mx[v],maxnum);
    }
    mx[u]=max(maxnum,sum[u]);
}

int main(){
    int n;cin>>n;
    rep(i,1,n){
        cin>>w[i];
    }
    rep(i,1,n-1){
        int x,y;cin>>x>>y;
        son[x].push_back(y);
        son[y].push_back(x);
    }
    dfs(1,0);
    if(ans==-INF)cout<<"Error\n";
    else cout<<ans<<endl;
    system("pause");
    return 0;
}