0分全WA 蒟蒻求调QAQ
查看原帖
0分全WA 蒟蒻求调QAQ
877156
yyy_Logic楼主2023/8/2 21:01
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define pii pair<int,int>
#define endl '\n'
#define test printf("\ntest\n")
#define int long long int
/*·········································*/
const int N = 2e5+10;
int n,x[N],y[N],fa[N][20],dep[N],lg[N],lm;
ll v1[N],v2[N],ans[N],res;
vector<int>g[N],le[N];


inline int read(){
	char c=getchar();
	int x=0,f=1;
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return f*x;
}
inline void write(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void dfs(int now,int fath){
	dep[now]=dep[fath]+1,fa[now][0]=fath;
	lm=max(lm,dep[now]);
	le[dep[now]].push_back(now);//差分
	for(int i=1;(1<<i)<=dep[now];i++)
		fa[now][i]=fa[fa[now][i-1]][i-1];
	for(int i=0;i<g[now].size();i++)
		if(g[now][i]!=fath)
			dfs(g[now][i],now);
}
inline int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	while(dep[x]>dep[y]){
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y)
		return x;
	//一起向上跳
	for(int k=lg[dep[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[x][k])
			x=fa[x][k],y=fa[y][k];
	}
	return fa[x][0];
}
inline void solve()
{
	int n=read();
	for(int i=1;i<=n-1;i++){
		x[i]=read(),y[i]=read(),v1[i]=read(),v2[i]=read();
		g[x[i]].push_back(y[i]),g[y[i]].push_back(x[i]);
	}
	lg[1]=1;
	for(int i=1;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	dfs(1,0);//倍增预处理
	for(int i=1;i<n;i++){
		ans[i]++;ans[i+1]++;
		ans[lca(i,i+1)]-=2;
	}
	for(int i=lm;i>1;i--){
		for(int j=0;j<le[i].size();j++){
			ans[fa[le[i][j]][0]]+=ans[le[i][j]];
		}
	}
	for(int i=1;i<n;i++){
		ll as;
		if (dep[x[i]]>dep[y[i]])
			as=ans[x[i]];
		else
			as=ans[y[i]];
		if(as*v1[i]<v2[i])
			res+=as*v1[i];
		else
			res+=v2[i];
	}
	cout<<res;
//	puts("");
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;
//	t=read();
	while(t--) solve();
	return 0;
}
2023/8/2 21:01
加载中...