小Biu的树(树形dp)
题目描述
小Biu有一颗有根树，树上有n个节点（编号1~n）。其中每个节点有一个苹果，每个苹果有一定的能量，现在小Biu和小Piu分别选出一棵子树，要求两棵子树不能相交而且所有苹果的能量和最大。
输入
第一行输入一个正整数 n(1 <= n <= 10^5)，表示树的结点个数。
第二行输入n个数，为 n个苹果的能量值 a[i](-10^4 <= a[i] <= 10^4)。
接下来 n – 1每行输入两个数 u 和 v (1 <= u,v <= n)，表示 u 和 v 之间有一条边。
保证 1 号结点为根节点。
第二行输入n个数，为 n个苹果的能量值 a[i](-10^4 <= a[i] <= 10^4)。
接下来 n – 1每行输入两个数 u 和 v (1 <= u,v <= n)，表示 u 和 v 之间有一条边。
保证 1 号结点为根节点。
输出
如果找不出两颗不相交的子树，输出 Impossible。
否则，输出找出的两颗不相交子树所有苹果的能量和。
否则，输出找出的两颗不相交子树所有苹果的能量和。
样例输入 Copy
8
0 5 -1 4 3 2 6 5
1 2
2 4
2 5
1 3
3 6
6 7
6 8样例输出 Copy
25提示
如图所示，分别选出4-2-5和7-6-8两棵子树，则所得能量和最大。
能量和=4+5+3+6+2+5=25
对于25%的数据,1<=n<=10
对于50%的数据,1<=n<=100
对于75%的数据,1<=n<=1000
对于100%的数据,1<=n<=100000
思路：求两颗不相交的子树，最大的权值和。关键是判断相交。如果dp[x]!=-inf,则可以更新答案。
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define per(i , a , b) for(register int i=(a);i>=(b);i--)
#define ms(s) memset(s, 0, sizeof(s))
#define squ(x) (x)*(x)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll , ll> pi;
typedef unordered_map<int,int> un_map;
typedef priority_queue<int> prque;
template<class T>
inline void read (T &x) {
x = 0;
int sign = 1;
char c = getchar ();
while (c < '0' || c > '9') {
if ( c == '-' ) sign = - 1;
c = getchar ();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar ();
}
x = x * sign;
}
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = ll(1e18);
const int mod = 1e9+7;
const double PI = acos(-1);
//#define LOCAL
int n;
ll a[maxn];
std::vector<int> e[maxn];
ll ans =-INF;
ll dp[maxn];
ll sum[maxn];
void dfs(int x,int fa) {
int siz = e[x].size();
sum[x]=a[x];
rep(i,0,siz-1) {
int y = e[x][i];
if(y==fa) continue;
dfs(y,x);
sum[x]+=sum[y];
if(dp[x]>-INF) ans=max(ans,dp[x]+dp[y]);
dp[x]=max(dp[x],dp[y]);
}
dp[x]=max(dp[x],sum[x]);
}
int main(int argc, char * argv[])
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
read(n);
rep(i,1,n) read(a[i]);
rep(i,1,n-1) {
int x,y;
read(x);read(y);
e[x].push_back(y);
e[y].push_back(x);
}
rep(i,1,n) dp[i]=-INF;
dfs(1,-1);
if(ans==INF) puts("Impossible");
else printf("%lld\n",ans);
return 0;
}