求助
查看原帖
求助
314829
sandunder楼主2022/7/17 20:29

只有subtask0的一个点对,帮忙看看qwq

#include <iostream>
#include <vector>
class node
{
	public:
		node(long long to_=0,long long e_=0,long long w_=0):to(to_),e(e_),w(w_)
		{
		};
		long long to,e,w;
};
long long c[200005];
std::vector<node>edge[200005];
long long father[200005][40],depth[200005];
void dfs(long long x,long long fa)
{
	father[x][0]=fa;
	depth[x]=depth[fa]+1;
	for(long long i=0; i<edge[x].size(); i++)
	{
		if(edge[x][i].to!=fa)
		{
			dfs(edge[x][i].to,x);
		}
	}
	for(long long i=1; (1<<i)<=depth[x]; i++)
	{
		father[x][i]=father[father[x][i-1]][i-1];
	}
}
long long lca(long long x,long long y)
{
	if(depth[x]<depth[y])
	{
		std::swap(x,y);
	}
	for(long long i=35; i>=0; i--)
	{
		if(depth[father[x][i]]>=depth[y])
		{
			x=father[x][i];
		}
		if(x==y)
		{
			return x;
		}
	}
	for(long long i=35; i>=0; i--)
	{
		if(father[x][i]!=father[y][i])
		{
			x=father[x][i];
			y=father[y][i];
		}
	}
	return father[x][0];
}
long long ans=0;
void query(long long x)
{
	long long fa=0;
	for(long long i=0; i<edge[x].size(); i++)
	{
		if(edge[x][i].to!=father[x][0])
		{
			query(edge[x][i].to);
			c[x]+=c[edge[x][i].to];
		}
		else
		{
			fa=i;
		}
	}
	ans+=std::min(edge[x][fa].e*c[x],edge[x][fa].w);
}

int main()
{
	long long n;
	std::cin>>n;
	for(long long i=1; i<n; i++)
	{
		long long u,v,e,w;
		std::cin>>u>>v>>e>>w;
		edge[u].push_back(node(v,e,w));
		edge[v].push_back(node(u,e,w));
	}
	dfs(1,0);
	for(long long i=2; i<=n; i++)
	{
		long long l=lca(i-1,i);
		c[l]-=2;
		c[i-1]++;
		c[i]++;
	}
	query(1);
	std::cout<<ans<<std::endl;
}

谢谢qwq

2022/7/17 20:29
加载中...