链接：https://ac.nowcoder.com/acm/contest/558/G
来源：牛客网
路径
小猫在研究树。
小猫在研究路径。
给定一棵N个点的树，每条边有边权，请你求出最长的一条路径，满足经过每个点最多一次，经过的边的条数为偶数，且边权和最大。
请输出这个最大的边权和。
输入描述:
第一行一个正整数N，表示节点个数。 接下来N−1行，第i行三个正整数 ui,vi,wi，表示第i条边连接点ui,vi，边权为wi。
输出描述:
一行一个正整数，表示最大的边权和。
备注:
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;
}