#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct node{int y,f1,f2;};
vector<node>G[N];
int dep[N],st[N][20],d[N],ans,D;
void dfs1(int x,int f)
{
	dep[x]=dep[f]+1;
	st[x][0]=f;for(int i=1;i<=D;i++)st[x][i]=st[st[x][i-1]][i-1];
	for(auto i:G[x])if(i.y!=f)dfs1(i.y,x); 
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=D;i>=0;i--)if(dep[st[x][i]]>=dep[y])x=st[x][i];
	if(x==y)return x;
	for(int i=D;i>=0;i--)if(st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
	return st[x][0];
}
void dfs2(int x,int f)
{
	for(auto i:G[x])if(i.y!=f)
	{
		dfs2(i.y,x);
		d[x]+=d[i.y];
	}
}
void dfs3(int x,int f)
{
	for(auto i:G[x])if(i.y!=f)
	{
		ans+=min(i.f1*d[i.y],i.f2);
		dfs3(i.y,x);
	}
}
signed main()
{
	int n;cin>>n;D=log2(n);
	for(int i=1;i<n;i++)
	{
		int x,y,f1,f2;cin>>x>>y>>f1>>f2;
		G[x].push_back({y,f1,f2});
		G[y].push_back({x,f1,f2});
	}
	dfs1(1,0);
	for(int i=1;i<n;i++)
	{
		int l=lca(i,i+1);
		d[i]++;d[i+1]++;d[l]-=2;
	}
	dfs2(1,0);
	dfs3(1,0);
	cout<<ans<<'\n';
	return 0;
}

原题传送门

前置知识：

1. P3379 【模板】最近公共祖先（LCA）
2. 树上差分——P3128 [USACO15DEC]Max Flow P

考虑这样一个性质：如果你第一次走过一条边买了多程票，就不会再买这条边的单程票。反之亦然。

所以对于每一条边，我们一定只买单程票或多程票。

于是只要求出每条边经过的次数 $k$ ，然后算出你需要花在这条边上的最少花费 $\min(k\times c_{i1},c_{i2})$ 统计进答案。

每条边经过的次数用树上差分搞，由于是边差分，直接在 $val_{\operatorname{lca(u,v)}}$ 上减两次。

Code

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N=2e5+10;

int n,fir[N],tot,fa[N][40],dep[N];
long long ans,val[N];
struct node {int to,nex,oned,twod;} e[N << 1];

void add(int u,int v,int xgf,int xrc)
{
	e[++tot].to=v;
	e[tot].oned=xgf;//这是两位同级机房神仙的名字
	e[tot].twod=xrc;
	e[tot].nex=fir[u];
	fir[u]=tot;
	return ;
}
void swap(int &x,int &y) {x^=y^=x^=y; return ;}

void dfs(int x,int dad)//LCA预处理
{
	dep[x]=dep[dad]+1;
	fa[x][0]=dad;
	for(int i=1;(1<<i)<=dep[x];i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=fir[x];i;i=e[i].nex)
		if(e[i].to^dad) dfs(e[i].to,x);
	return ;
}

int lca(int x,int y)//倍增求LCA
{
	if(dep[x] < dep[y]) swap(x,y);
	for(int i=35;i>=0;i--)
	{
		if(dep[fa[x][i]] >= dep[y]) x=fa[x][i];
		if(x == y) return y;
	}
	for(int i=35;i>=0;i--)
		if(fa[x][i]^fa[y][i]) {x=fa[x][i]; y=fa[y][i];}
	return fa[x][0];
}

void solve(int x)
{
	int u;
	for(int i=fir[x];i;i=e[i].nex)
		if(e[i].to^fa[x][0])
		{
			solve(e[i].to);
			val[x]+=val[e[i].to];//统计经过的次数
		}
		else u=i;
	if(e[u].oned*val[x] < e[u].twod) ans+=e[u].oned*val[x];
	else ans+=e[u].twod;//统计答案
	return ;
}

int main()
{
//	freopen("work.in","r",stdin); freopen("work.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,u,v,c1,c2;i<n;i++)
	{
		scanf("%d%d%d%d",&u,&v,&c1,&c2);
		add(u,v,c1,c2); add(v,u,c1,c2);
	}
	dfs(1,0);
	for(int i=1;i<n;i++)
	{
		val[i]++; val[i+1]++;
		val[lca(i,i+1)]-=2;//树上差分，题目要求编号从小到大访问
	}
	solve(1);
	printf("%lld",ans);
//	fclose(stdin); fclose(stdout);
	return 0;
}

感谢阅读！您的点赞和留言是对作者最大的支持！