树的路径长度(daan)(新手勿入)(狗头)

zhangyihao 2022-02-09 20:09:06 2022-02-09 20:10:00 0
#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int n,s,W[maxn],np=0,first[maxn];
int dist[maxn],zz;
struct edge
{
	int to,next;
	int L;
}E[maxn<<1];
void add(int u,int v,int L)
{
	E[++np]=(edge){v,first[u],L};
	first[u]=np;
}
void DFS(int i,int f,int d)
{
	dist[i]=d;
	for(int p=first[i];p;p=E[p].next)
	{
		int j=E[p].to;
		if(j==f)continue;
		DFS(j,i,d+E[p].L);
	}
}
void solve1()
{
	long long sum=0;
	zz=dist[1];
	for(int i=1;i<=n;i++)
	{
		sum+=dist[i];
		if(dist[i]>zz)
		  zz=dist[i];	
	}
	printf("%lld\n",sum);
}
void solve2()
{
	cout<<zz;
	for(int i=1;i<=n;i++)
	{
		if(dist[i]==zz)
		  	cout<<" "<<i;
	}
	cout<<endl;
}
void solve3()
{
	long long sum=0;
	for(int i=1;i<=n;i++)sum+=(long long)dist[i]*W[i];
	printf("%lld\n",sum);
}
int main()
{
	int u,v,L;
	scanf("%d%d",&n,&s);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&L);
		add(u,v,L);
		add(v,u,L);
	}
	for(int i=1;i<=n;i++)scanf("%d",&W[i]);
	DFS(s,0,0); 
	solve1();
	solve2();
	solve3();
	return 0;
}
{{ vote && vote.total.up }}

共 5 条回复

root 站长

这个题是哪里的,我没有哇。。。

zhangyihao

我好通过一下,刷一下排行

zhangyihao

老师,你把这个题发出来吧

root 站长

🐱

root 站长

🐶