DP(樹型專題5)

題意:給定一棵樹, 然後咱們可以給每條邊權重1, 現要求: 使得從根節點到每個葉子結點的權和是相同的, 問咱們至少要加幾次權;

P1131 [ZJOI2007]時态同步

strategy : 顯然, 咱們得維護每個子樹的最大權, 然後修改所有路徑使得權和等于最大權, 于是想到dfs搜最大權, 每個節點的貢獻都是 m[cur] - way[i].cost - m[way[i].to]

感覺根本不是dp

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define id(x) ((x + 8))
#define bin(x) cerr << #x << " is " << bitset<15>(x) << endl
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 5e5 + 10;
int cnt, head[maxn], n, root, f, t, c, m[maxn];
ll ans = 0;
struct node
{
	int cost, nxt, to;
} way[maxn];
void addedge(int from, int to, int cost)
{
	way[++cnt].cost = cost;
	way[cnt].to = to;
	way[cnt].nxt = head[from];
	head[from] = cnt;
}
void dfs(int cur, int fa)
{
	for (int i = head[cur]; i; i = way[i].nxt) {
		int to = way[i].to;
		if(to == fa)continue;
		dfs(to, cur);
		m[cur] = max(m[cur], way[i].cost + m[to]);
	}
	for (int i = head[cur]; i; i = way[i].nxt) {
		if(way[i].to == fa)continue;
		ans += m[cur] - way[i].cost - m[way[i].to];
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin >> n >> root;
	_rep(i, 1, n - 1)
	{
		cin >> f >> t >> c;
		addedge(f, t, c);
		addedge(t, f, c);
	}
	dfs(root, -1);
	cout << ans << endl;
}