树的直径 树形dp+2次dfs

 

题目描述

给定一棵树 T ，树 T 上每个点都有一个权值。

定义一颗树的子链的大小为：这个子链上所有结点的权值和 。

请在树 T 中找出一条最大的子链并输出。

输入描述:

第一行输入一个 n,1≤n≤105。

接下来一行包含n个数，对于每个数 ai,−10^5≤ai≤10^5，表示 i 结点的权值。

接下来有n-1行，每一行包含两个数u，v（ 1≤u,v≤n , u != v），表示u与v之间有一条边。

输出描述:

仅包含一个数，表示我们所需要的答案。

示例1

输入

5
2 -1 -1 -2 3
1 2
2 3
2 4
2 5

输出

4

说明

样例中最大子链为1 -> 2 -> 5

备注:

一个结点，也可以称作一条链

 树形dp：

如果值在边上的话

void DP(int u,int pa)
{
    dp[u]=0;
    for(int i=h[u];i;i=ne[i])
    {
        int v=e[i];
        if(v==pa) continue;
        DP(v,u);
        ans=max(ans,dp[u]+dp[v]+dis[i]);
        dp[u]=max(dp[u],dp[v]+dis[i]);
    }
}
 

如果值在点上的话

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int N=1e5+10;
int n;
ll idx,e[N*2],h[N],ne[2*N],w[N],dp[N],ans;
bool vis[N];
void add(int x,int y)
{
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}
void dfs(int x)
{
    dp[x]=w[x];
    vis[x]=1;
    ans=max(ans,w[x]);
    for(int i=h[x]; ~i; i=ne[i])
    {
        int j=e[i];
        if(vis[j])continue;
        dfs(j);
        ans=max(ans,dp[x]+dp[j]);
        dp[x]=max(dp[x],dp[j]+w[x]);
    }
}
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    memset(h,-1,sizeof h);
    ans=-INF;
    for(int i=1; i<=n; i++)
    {
        cin>>w[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1);
    cout<<ans;
    return 0;
}

两次dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int N=1e5+10;
int n,pos;
ll idx,e[N*2],h[N],ne[2*N],w[N],dp[N],ans;
bool vis[N];
void add(int x,int y)
{
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}
void dfs(int now,ll x)
{
    vis[now]=1;
    if(ans<x)
    {
        ans=x;
        pos=now;
    }
    for(int i=h[now]; ~i; i=ne[i])
    {
        int j=e[i];
        if(vis[j])continue;
        dfs(j,x+w[j]);
    }
}
int  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    memset(h,-1,sizeof h);
    ans=-INF;
    for(int i=1; i<=n; i++)
    {
        cin>>w[i];
    }
    for(int i=1; i<=n-1; i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,w[1]);
    //cout<<ans;
    memset(vis,0,sizeof vis);
    dfs(pos,w[pos]);
    cout<<ans;
    return 0;
}