首页 > 其他分享 >P2986 Great Cow Gathering G

P2986 Great Cow Gathering G

时间:2023-04-01 17:45:33浏览次数:42  
标签:sz Great nxt int Gathering fa go P2986 hd

 

换根dp, father -> son  , 基本是加减

 

#include <bits/stdc++.h>
using namespace std ;
 const int N=1e5+2,M=N*5;
 #define int long long
 int n,a[N],sz[N],g[N],f[N],S;
 int nxt[M],go[M],w[M],hd[N],all;
 
 void add(int x,int y,int z){
 	go[++all]=y,nxt[all]=hd[x],w[all]=z;
	hd[x]=all;
 }
 void d0(int x,int fa){
 	int i,y,z;
 	sz[x]=a[x];
 	
	  for(i=hd[x];i;i=nxt[i]){
 		 y=go[i],z=w[i]; 
		 if(y!=fa) d0(y,x),sz[x]+=sz[y];
 	  }
 	  for(i=hd[x];i;i=nxt[i]){
	  	y=go[i],z=w[i];
	  	if(y!=fa) g[x]+=g[y]+sz[y]*z;
	  }
 }
 
 void dfs(int x,int fa){
 	int i,y,z;
 	
	  for(i=hd[x];i;i=nxt[i]){
 		 y=go[i],z=w[i]; 
		 if(y!=fa){
		 	f[y]=f[x]-z*sz[y]+z*(S-sz[y]);
		 	dfs(y,x);
		 }
 	  }
 }
 signed main(){
 	int i,x,y,z,t=1e9;
 	cin>>n;
 	for(i=1;i<=n;i++) cin>>a[i],S+=a[i];
 	for(i=1;i<n;i++) cin>>x>>y>>z,add(x,y,z),add(y,x,z);
 	d0(1,0);
    dfs(1,0);
 	
 	for(i=1;i<=n;i++) t=min(t,f[i]);
 	
 	cout<<t+g[1]<<'\n';
 }
 
 

 

标签:sz,Great,nxt,int,Gathering,fa,go,P2986,hd
From: https://www.cnblogs.com/towboa/p/17278986.html

相关文章

  • Mac 上启动nacos 出现异常java.lang.IllegalArgumentException: the length of secret
    这个异常提示是因为Nacos的配置中加密相关的参数未正确填写所导致的。我们只需要找到nacos/conf/application.properties文件,然后给nacos.core.auth.plugin.nacos.token.secret.key这个属性配置一个大于32位的随机字符串即可这个字符串大家可以在jwt的官网去生成:https://jwt.......
  • 538. Convert BST to Greater Tree
    GivenaBinarySearchTree(BST),convertittoaGreaterTreesuchthateverykeyoftheoriginalBSTischangedtotheoriginalkeyplussumofallkeysgrea......
  • The Great Mixing CF788C
    从序列中找一些数,使平均数>=m,问最少取几个数》  每个数-m,题目即求和>=0最少取多少数?背包问题 #include<iostream>#include<algorithm>#include<cst......
  • 在统信UOS上二进制安装GreatSQL
    GreatSQL社区原创内容未经授权不得随意使用,转载请联系小编并注明来源。GreatSQL是MySQL的国产分支版本,使用上与MySQL一致。作者:vatebur文章来源:GreatSQL社区投稿UOS......
  • “采访”ChatGPT看看它对我们GreatSQL社区有什么看法
    什么是ChatGPT?ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类......
  • Number of Great Partitions
    NumberofGreatPartitionsYouaregivenanarray nums consistingofpositive integersandaninteger k .Partitionthearrayintotwoorderedgroups suc......
  • UVA10256 The Great Divide
    洛谷传送门UVA传送门考虑对两个点集求出凸包,显然如果这两个凸包相离就合法,然后问题就转化成了这两个凸包是否有交。设红点凸包包围的点集为\(A\),蓝点凸包包围的点集为......
  • Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)
    题目链接思路首先看到这种求\(x^k\)形式的,直接无脑转下降幂:\(x^k=\sum_{i=1}^kS2(k,i)\cdotx^{\underline{i}}\),其中\(S2\)表示第二类斯特林数,\(x^{\underlinei}\)表......
  • Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)
    题目链接思路首先看到这种求\(x^k\)形式的,直接无脑转下降幂:\(x^k=\sum_{i=1}^kS2(k,i)\cdotx^{\underline{i}}\),其中\(S2\)表示第二类斯特林数,\(x^{\underlinei}\)表......
  • Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)
    题目链接思路首先看到这种求\(x^k\)形式的,直接无脑转下降幂:\(x^k=\sum_{i=1}^kS2(k,i)\cdotx^{\underline{i}}\),其中\(S2\)表示第二类斯特林数,\(x^{\underlinei}\)表......