fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<int,int> P;
  7. typedef pair<int,P> P1;
  8. typedef pair<P,P> P2;
  9. #define pu push
  10. #define pb push_back
  11. #define mp make_pair
  12. #define eps 1e-7
  13. #define INF 1000000000
  14.  
  15. #define fi first
  16. #define sc second
  17. #define rep(i,x) for(int i=0;i<x;i++)
  18. #define repn(i,x) for(int i=1;i<=x;i++)
  19. #define SORT(x) sort(x.begin(),x.end())
  20. #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
  21. #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
  22. #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
  23.  
  24. const ll mod = 998244353;
  25.  
  26. priority_queue<ll,vector<ll>,greater<ll>>up[200005], mid[200005], dw[200005];
  27. ll lazyup[200005],lazymid[200005],lazydw[200005];
  28.  
  29. int n,k;
  30. vector<P>edge[200005];
  31. void look(priority_queue<ll,vector<ll>,greater<ll>>&que,ll x){
  32.     vector<ll>vec;
  33.     while(que.size()){ vec.pb(que.top()); que.pop(); }
  34.     reverse(vec.begin(),vec.end());
  35.     for(auto v:vec) cout << v+x << " ";
  36.     cout << endl;
  37.     for(auto v:vec) que.push(v);
  38. }
  39. void dfs(int v,int u){
  40. 	P mx = mp(0,0);
  41. 	rep(i,edge[v].size()){
  42. 		if(edge[v][i].fi == u) continue;
  43. 		dfs(edge[v][i].fi,v);
  44. 		if(mx < mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi)){
  45. 			mx = mp((int)(up[edge[v][i].fi].size() + mid[edge[v][i].fi].size() + dw[edge[v][i].fi].size()), edge[v][i].fi);
  46. 		}
  47. 	}
  48. 	if(mx.sc == 0){
  49. 		up[v].push(0);
  50. 		return;
  51. 	}
  52. 	else{
  53. 		swap(up[v],up[mx.sc]);
  54. 		swap(mid[v],mid[mx.sc]);
  55. 		swap(dw[v],dw[mx.sc]);
  56. 		lazyup[v] = lazyup[mx.sc];
  57. 		lazymid[v] = lazymid[mx.sc];
  58. 		lazydw[v] = lazydw[mx.sc];
  59. 	}
  60. 	rep(i,edge[v].size()){
  61. 	    if(edge[v][i].fi == mx.sc){
  62. 	        lazyup[v] += 2 * edge[v][i].sc;
  63. 	        lazydw[v] -= 2 * edge[v][i].sc;
  64. 	        break;
  65. 	    }
  66. 	}
  67. 	rep(i,edge[v].size()){
  68. 		if(edge[v][i].fi == u) continue;
  69. 		if(edge[v][i].fi == mx.sc) continue;
  70. 		while(up[edge[v][i].fi].size()){
  71. 			ll x = up[edge[v][i].fi].top() + lazyup[edge[v][i].fi] + 2 * edge[v][i].sc;
  72. 			up[v].push(x - lazyup[v]);
  73. 			up[edge[v][i].fi].pop();
  74. 		}
  75. 		while(mid[edge[v][i].fi].size()){
  76. 			ll x = mid[edge[v][i].fi].top() + lazymid[edge[v][i].fi];
  77. 			up[v].push(x - lazyup[v]);
  78. 			mid[edge[v][i].fi].pop();
  79. 		}
  80. 		while(dw[edge[v][i].fi].size()){
  81. 			ll x = dw[edge[v][i].fi].top() + lazydw[edge[v][i].fi] - 2 * edge[v][i].sc;
  82. 			up[v].push(x - lazyup[v]);
  83. 			dw[edge[v][i].fi].pop();
  84. 		}
  85. 	}
  86. 	up[v].push(-lazyup[v]);
  87. 	while(up[v].size() > k/2){
  88. 		ll x = up[v].top() + lazyup[v]; up[v].pop();
  89. 		mid[v].push(x - lazymid[v]);
  90. 	}
  91. 	while(mid[v].size() > k%2){
  92. 		ll x = mid[v].top() + lazymid[v]; mid[v].pop();
  93. 		dw[v].push(x - lazydw[v]);
  94. 	}
  95. 	//cout << v << "_______" << endl;
  96. 	//look(up[v],lazyup[v]);
  97. 	//look(mid[v],lazymid[v]);
  98. 	//look(dw[v],lazydw[v]);
  99. }
  100. void solve(){
  101.     scanf("%d%d",&n,&k);
  102.     repn(i,n){
  103.         while(up[i].size()) up[i].pop();
  104.         while(mid[i].size()) mid[i].pop();
  105.         while(dw[i].size()) dw[i].pop();
  106.         edge[i].clear();
  107.         lazyup[i] = lazymid[i] = lazydw[i] = 0;
  108.     }
  109.     rep(i,n-1){
  110.     	int a,b,c;
  111.     	scanf("%d%d%d",&a,&b,&c);
  112.     	edge[a].pb(mp(b,c));
  113.     	edge[b].pb(mp(a,c));
  114.     }
  115.     if(k == 1){
  116.     	puts("0");
  117.     	return ;
  118.     }
  119.     dfs(1,-1);
  120.     ll ans = 0;
  121.     int use = 0;
  122.     vector<ll>vec;
  123.     while(up[1].size()){ vec.pb(up[1].top() + lazyup[1]); up[1].pop(); use++; }
  124.     while(mid[1].size()){ vec.pb(mid[1].top() + lazymid[1]); mid[1].pop(); use++; }
  125.     while(dw[1].size()){ vec.pb(dw[1].top() + lazydw[1]); dw[1].pop(); use++; }
  126.     sort(vec.begin(),vec.end(),greater<ll>());
  127.     rep(i,k) ans += vec[i];
  128. 	//assert(use == k);
  129. 	printf("%lld\n",ans);
  130. }
  131. int main(){
  132. 	int t; scanf("%d",&t);
  133. 	while(t--) solve();
  134. }
Success #stdin #stdout 0.01s 27232KB
comments (?)
stdin
copy 
1
5 3
1 2 4
1 3 1
1 4 8
4 5 9
stdout
copy 
44
https://ideone.com/AmLhRp
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!