代码源 - 树上路径1

树上路径1

给你一个 \(n(1≤n≤2000)\)个点的树。

给你 \(m(1≤m≤2000)\) 条树上的简单路径，每个路径有个权值 \(a_i(1≤a_i≤109)\)。

要求选择一些路径，使得每个点至多在一条路径上，并且路径的权值和最大。

输入格式

第一行两个整数n, m。

接下来一行n−1个数，\(f_2,f_3,…,f_n\)，其中\(f_i(1≤f_i<i)\)表示 \(i\) 的父亲节点。

接下来mm行每行三个整数，\(u,v,a_i(u≠v)\)，表示一条路径和它的权值。

输出格式

一个整数，表示答案。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e3 + 10;
const ll INF = 1ll << 60;
vector<vector<int> > G(N);
vector<array<int, 3> > path[N];
int n, m;
int p[N];
int depth[N];
ll f[N], sf[N];

void dfs(int u)
{
	for (auto v : G[u])
	{
		dfs(v);
		sf[u] += f[v];
	}
	f[u] = sf[u];
	for (auto pth : path[u])
	{
		ll tmp = sf[u];
		int x = pth[0];
		while(x != u)
		{
			tmp += sf[x] - f[x];
			x = p[x];
		}
		x = pth[1];
		while(x != u)
		{
			tmp += sf[x] - f[x];
			x = p[x];
		}
		tmp += pth[2];
		f[u] = max(f[u], tmp);
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 2; i <= n; i++)
	{
		scanf("%d", &p[i]);
		G[p[i]].push_back(i);
		depth[i] = depth[p[i]] + 1;
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v, a;
		scanf("%d%d%d", &u, &v, &a);
		int x = u, y = v;
		while(x != y)
		{
			if (depth[x] > depth[y]) x = p[x];
			else y = p[y];
		}
		path[x].push_back({u, v, a});
	}
	dfs(1);
	printf("%lld\n", f[1]);
    return 0;
}