全RE求调
查看原帖
全RE求调
763878
Jerry_heng楼主2024/2/29 21:14
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,fa[41][200010],cnt,head[200010],s[200010],ans,dep[200010];
struct node{
	int to,nxt,c1,c2;
}edge[400010];
void add(int u,int v,int c1,int c2){
	edge[++cnt]=(node){v,head[u],c1,c2};
	head[u]=cnt;
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=40;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
	if(u==v)return v;
	for(int i=40;i>=0;i--)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void dfs1(int u,int f){
	fa[u][0]=f,dep[u]=dep[f]+1;
	for(int i=1;i<=40;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f)continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int f){
	int e;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f){
			e=i;
			continue;
		}
		dfs2(v,u);
		s[u]+=s[v];
	}
	ans+=min(edge[e].c2,edge[e].c1*s[u]);
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int u,v,c1,c2;
		scanf("%lld%lld%lld%lld",&u,&v,&c1,&c2);
		add(u,v,c1,c2),add(v,u,c1,c2);
	}
	dfs1(1,0);
	for(int i=2;i<=n;i++){
		int u=i-1,v=i;
		int f=LCA(u,v);
		s[u]++,s[v]++,s[f]-=2ll;
	}
	dfs2(1,0);
	printf("%lld\n",ans);
	return 0;
}
2024/2/29 21:14
加载中...