思路:dp[i]表示以i为根节点的子链最大值是多少,u为根时,v为u的子节点,我们可以让u和v两条链相连可得,res=max(res,dp[u]+dp[v]),在dfs的时候不断合并两条链取最大值,然后我们再更新此时u这条链,dp[u]=max(dp[u],a[u]+dp[v]),因为可能全为负数所以我们每次最开始取一次最大值。
#include <cstdio> #include <cstring> #include <algorithm> #include <set> #include<iostream> #include<vector> #include<queue> #include<stack> #include<bits/stdc++.h> using namespace std; typedef long long ll; #define SIS std::ios::sync_with_stdio(false) #define space putchar(' ') #define enter putchar('\n') #define lson root<<1 #define rson root<<1|1 typedef pair<int,int> PII; const int mod=998244353; const int N=2e6+10; const int M=2e5+10; const int inf=0x7f7f7f7f; const int maxx=2e5+7; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } ll lcm(ll a,ll b) { return a*(b/gcd(a,b)); } template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar('0' + x % 10); } ll qsm(int a,int b,int p) { ll res=1%p; while(b) { if(b&1) res=res*a%p; a=1ll*a*a%p; b>>=1; } return res; } struct node { int to,nex,w; }edge[M]; struct tr { int l,r; }tre[M]; int head[M]; int tot; vector<int> G[M]; ll dp[M]; ll a[M]; ll res=-inf; int vis[M]; void add(int u,int v) { edge[++tot].to=v; //edge[tot].w=w; edge[tot].nex=head[u]; head[u]=tot; } void dfs(int u) { vis[u]=1; res=max(res,a[u]); dp[u]=a[u]; for(int i=head[u];~i;i=edge[i].nex) { int v=edge[i].to; if(!vis[v]) { dfs(v); res=max(res,dp[u]+dp[v]); dp[u]=max(dp[u],dp[v]+a[u]); } } } int main() { // SIS; int n,q; memset(head,-1,sizeof head); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<n;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1); printf("%lld\n",res); return 0; }