fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. typedef double db;
  15. mt19937 mrand(random_device{}()); 
  16. const ll mod=1000000007;
  17. int rnd(int x) { return mrand() % x;}
  18. ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  19. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
  20. // head
  21.  
  22. const int N=201000;
  23. int n,u,v,w,rt,T,_,mt[N],cnt[N],k,pv[N],mark[N];
  24. ll ans;
  25. vector<PII> e[N];
  26. vector<array<ll,3>> dis;
  27.  
  28. void dfs(int u,int f,int br,ll d) {
  29. 	dis.pb({d,br,u});
  30. 	for (auto p:e[u]) {
  31. 		int v=p.fi;
  32. 		if (v==f) continue;
  33. 		dfs(v,u,br==rt?v:br,d+p.se);
  34. 	}
  35. }
  36.  
  37. void solve(int x) {
  38. 	rt=x;
  39. 	dis.clear();
  40. 	dfs(rt,0,rt,0);
  41. 	sort(all(dis)); reverse(all(dis));
  42. 	T++;
  43. 	ll tmp=0;
  44. 	int pt=0;
  45. 	for (auto x:dis) {
  46. 		if (mt[x[1]]!=T) mt[x[1]]=T,cnt[x[1]]=0;
  47. 		if (pt<k&&cnt[x[1]]<k/2) { pt++; cnt[x[1]]++; tmp+=x[0]; mark[x[2]]=T; }
  48. 	}
  49. 	if (pt==k&&tmp>ans) {
  50. 		ans=tmp; rt=x;
  51. 		rep(i,1,n+1) pv[i]=(mark[i]==T);
  52. 	}
  53. }
  54.  
  55. int q[N],f[N],vis[N],sz[N],ms[N];
  56. int find(int u) {
  57. 	int t=1;q[0]=u;f[u]=-1;
  58. 	rep(i,0,t) {
  59. 		u=q[i];
  60. 		rep(j,0,e[u].size()) {
  61. 			int v=e[u][j].fi;
  62. 			if (!vis[v]&&v!=f[u]) f[q[t++]=v]=u;
  63. 		}
  64. 		ms[q[i]]=0;
  65. 		sz[q[i]]=1;
  66. 	}
  67. 	for (int i=t-1;i>=0;i--) {
  68. 		ms[q[i]]=max(ms[q[i]],t-sz[q[i]]);
  69. 		if (ms[q[i]]*2<=t) return q[i];
  70. 		sz[f[q[i]]]+=sz[q[i]];
  71. 		ms[f[q[i]]]=max(ms[f[q[i]]],sz[q[i]]);
  72. 	}
  73. 	return 0;
  74. }
  75.  
  76. void gao(int u) {
  77. 	u=find(u);
  78. 	solve(u);
  79. 	T++;
  80. 	int maj=-1;
  81. 	rep(i,0,k) {
  82. 		auto x=dis[i];
  83. 	//	printf("dd %lld %lld %lld\n",x[0],x[1],x[2]);
  84. 		if (mt[x[1]]!=T) mt[x[1]]=T,cnt[x[1]]=0;
  85. 		cnt[x[1]]++;
  86. 		if (cnt[x[1]]>k/2) maj=x[1];
  87. 	}
  88. 	vis[u]=1;
  89. 	//fprintf(stderr,"%d %d\n",u,maj);
  90. 	if (maj!=-1&&!vis[maj]) gao(maj);
  91. }
  92.  
  93. pair<ll,int> dfs(int u,int f) {
  94. 	int fv=pv[u];
  95. 	ll mdis=0;
  96. 	for (auto p:e[u]) {
  97. 		int v=p.fi;
  98. 		if (v==f) continue;
  99. 		auto z=dfs(v,u);
  100. 		if (z.se<k/2) z.fi+=p.se;
  101. 		fv+=z.se;
  102. 		mdis=max(mdis,z.fi);
  103. 	}
  104. 	if (pv[u]) mdis=-(1ll<<60);
  105. 	return mp(mdis,fv);
  106. }
  107.  
  108. void solve() {
  109. 	scanf("%d%d",&n,&k);
  110. 	rep(i,1,n+1) e[i].clear(),vis[i]=0;
  111. 	ans=0;
  112. 	for (int i=1;i<n;i++) {
  113. 		scanf("%d%d%d",&u,&v,&w);
  114. 		e[u].pb(mp(v,w));
  115. 		e[v].pb(mp(u,w));
  116. 	}
  117. 	if (k%2==1) {
  118. 		--k;
  119. 		gao(1);
  120. 		ans+=dfs(rt,0).fi;
  121. 	} else gao(1);
  122. 	printf("%lld\n",2*ans);	
  123. }
  124.  
  125. int main() {
  126. 	for (scanf("%d",&_);_;_--) solve();
  127. }
  128.  
Success #stdin #stdout 0s 8236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hIy3cZ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!