自动搬运

查看原文

来自洛谷，原作者为

	MY（一名蒟蒻） 你数据结构都用错了，怎么改都是没用的。

搬运于2025-08-24 22:24:46，当前版本为作者最后更新于2021-02-15 16:43:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

前置知识：

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;
}

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