G.路径 【树形DP】 【牛客】【桂林电子科技大学第三届ACM程序设计竞赛】

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

请输出这个最大的边权和。

传送门

比赛以为 是要对个点都进行dfs，以为时间复杂度很大，看到树就怕了，没想到是一道树形DP

太菜了！！！

AC_code:

/*
Algorithm:树形DP 
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
ll dp[maxn][2];// 1代表奇数个节点  0代表偶数个节点 
struct edge{
	int v;
	int w;
};
vector<edge> g[maxn];
ll ans = 0;//答案
void dfs(int u, int fa) {
	dp[u][0] = -1e18;
	int len = g[u].size();
	for(int i = 0; i < len; i++){
		int v = g[u][i].v, w = g[u][i].w;
		if(v == fa) continue;
		dfs(v, u);
		ans = max(ans, dp[u][0] + dp[v][1] + w);
		ans = max(ans, dp[u][1] + dp[v][0] + w);
		dp[u][0] = max(dp[u][0], dp[v][1] + w);
		dp[u][1] = max(dp[u][1], dp[v][0] + w);
	}
	
}
int main() {
	int n;
	cin>>n;
	int u, v, w;
	for(int i = 1; i < n; i++){
		scanf("%d %d %d", &u, &v, &w);
		g[u].push_back(edge{v, w});
		g[v].push_back(edge{u, w});
	}
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}