牛客网 桂林电子科技大学第三届ACM程序设计竞赛 G.路径-带条件的树的直径变形-边权最大，边数偶数的树上的最长路径-树形dp

时间：2021-02-05 23:43:28

链接：https://ac.nowcoder.com/acm/contest/558/G

来源：牛客网

路径

小猫在研究树。
小猫在研究路径。
给定一棵N个点的树，每条边有边权，请你求出最长的一条路径，满足经过每个点最多一次，经过的边的条数为偶数，且边权和最大。
请输出这个最大的边权和。

输入描述:

第一行一个正整数N，表示节点个数。

接下来N−1行，第i行三个正整数

ui,vi,wi，表示第i条边连接点ui,vi，边权为wi。

输出描述:

一行一个正整数，表示最大的边权和。
示例1

输入

复制

5

1 2 5

1 3 5

2 4 5

2 5 1

输出

复制

10

备注:

1≤N≤10

5

,1≤w

i

≤10

9

，保证输入数据形成一棵树。

一开始智障了，以为直接搜索跑个树的直径然后删边就可以。最后发现想的太简单了，只能用树dp写。

二维dp，0表示偶数条边情况下，1表示奇数。

因为按边算，叶子节点为0，赋值0，1的赋值-inf，往上，到父节点，父节点的状态为，父亲的偶数情况为儿子节点的奇数情况+边权，奇数情况也一样。

dp[u][0]表示从叶子节点到当前节点u，偶数条边的最大值，奇数同理。到根节点的时候，偶数情况有两种：1.两个奇数条边的子树的链的和。2.两个偶数条边的子树的链的和。

代码:

 //G-树上的dp

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const ll inf=1e18+;

 ll dp[maxn+][];

 struct node{

     int to;

     ll val;

 };

 int n;

 ll ans=-inf;

 vector<node> G[maxn<<];

 bool vis[maxn];

 void dfs(int u)

 {

     vis[u]=true;

     for(int i=;i<G[u].size();i++){

         int v=G[u][i].to;

         ll w=G[u][i].val;

         if(vis[v]) continue;

         dfs(v);

         //两个端点相连的 奇数+奇数 或者偶数+偶数的

         ans=max(ans,dp[u][]+dp[v][]+w);

         ans=max(ans,dp[u][]+dp[v][]+w);

         dp[u][]=max(dp[u][],dp[v][]+w);

         dp[u][]=max(dp[u][],dp[v][]+w);

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;i++){

         int u,v;ll w;

         scanf("%d%d%lld",&u,&v,&w);

         G[u].push_back({v,w});

         G[v].push_back({u,w});

     }

     memset(vis,false,sizeof(vis));

     for(int i=;i<=n;i++){

         dp[i][]=;

         dp[i][]=-inf;

     }

     dfs();

     cout<<ans<<endl;

 }

相关文章