【题解】LuoGu6869：[COCI2019-2020#5] Putovanje

原题传送门
树上差分
就是走$n-1$条路
每次从$i$走到$i+1$，所以用树上差分进行路径覆盖

对于每条边可以直接买多程票，也可以买几次单程票

Code：

#include <bits/stdc++.h>
#define maxn 200010
#define LL long long
using namespace std;
LL delta[maxn], odd[maxn], even[maxn], ans;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], d[maxn], fa[maxn][25], n;
struct Line{
	int x, y, a, b;
}line[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){
	edge[++num] = (Edge){y, head[x]}, head[x] = num;
}

void dfs(int u, int pre){
	d[u] = d[pre] + 1, fa[u][0] = pre;
	for (int i = 0; fa[u][i]; ++i) fa[u][i + 1] = fa[fa[u][i]][i];
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u);
	}
}

int lca(int u, int v){
	if (d[u] < d[v]) swap(u, v);
	for (int i = 20; i >= 0; --i)
		if (d[u] - (1 << i) >= d[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i = 20; i >= 0; --i)
		if (fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

void calc(int u, int pre){
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			calc(v, u);
			delta[u] += delta[v];
		}
	}
	ans += min(even[u], delta[u] * odd[u]);
}

int main(){
	n = read();
	for (int i = 1; i < n; ++i){
		line[i].x = read(), line[i].y = read(), line[i].a = read(), line[i].b = read();
		addedge(line[i].x, line[i].y), addedge(line[i].y, line[i].x);
	}
	dfs(1, 0);
	for (int i = 1; i < n; ++i){
		int x = line[i].x, y = line[i].y;
		if (d[x] > d[y]) odd[x] = line[i].a, even[x] = line[i].b;
		else odd[y] = line[i].a, even[y] = line[i].b;
	}
	for (int i = 1; i < n; ++i){
		int x = i, y = i + 1;
		int z = lca(x, y);
		++delta[x], ++delta[y], delta[z] -= 2;
	}
	calc(1, 0);
	printf("%lldn", ans);
	return 0;
}

最后

以上就是腼腆小蝴蝶为你收集整理的【题解】LuoGu6869：[COCI2019-2020#5] Putovanje的全部内容，希望文章能够帮你解决【题解】LuoGu6869：[COCI2019-2020#5] Putovanje所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。