## G - As far as possible Editorial by en_translator

We will regard the given tree as a rooted tree rooted at \(1\).

We first consider Takahashi’s strategy.

For any edge on the tree, when the tree is split into two parts by the edge, if Aoki has chosen at least one vertex in the part not containing vertex \(1\), then Takahashi has to construct a walk that passes through that edge at least twice (back and forth). Conversely, he can construct the shortest such walk, which passes through such edges exactly twice but not the others. It can be constructed as, for example, an Euler tour on the tree obtained by removing unnecessary edges.

Based on this fact, we will try to solve the problem with tree DP (Dynamic Programming). For each subtree \(T_v\) rooted at vertex \(v\), let us try to find \((S_v(1), S_v(2), \ldots, S_v(T_v))\), defined as the minimum scores for \(K=1,2,\ldots,|T_v|\) when they play optimally on \(T_v\). Here, \(|T_v|\) denotes the number of vertices in \(T_v\).

If \(T_u\) consist of a single vertex, then \(|T_u|=1\) and \(S_u(1)=0\).

Suppose that vertex \(u\) has \(v_1,v_2,\ldots,v_c\) as its direct children, with the lengths of the edge between \(u\) and them being \(d_1,d_2,\ldots,d_c\), respectively, and the scores are already known for \(T_{v_i}\) \((1\leq i\leq c)\). Then, noticing it is useless to choose \(u\) if \(K<|T_u|\), the scores \(S(u,K)\) \((1\leq K < |T_u|)\) satisfy

\[ S(u,K)=\max_{x_1+x_2+\cdots+x_c=K}\sum_{i=1}^c \begin{cases} 0 & (x_i=0) \\ 2d_i+S(v_i,x_i) & (1\leq x_i\leq |T_i|), \end{cases} \]

where each \(x_i\) ranges over \(0\leq x_i\leq |T_i|\). Finally, \(S(u,|T_u|)=S(u,|T_u|-1)\). Since \(S(v,x)\leq S(v,x+1)\) for any \(v\), this can be interpreted as the maximum sum of a total of \(K\) elements chosen from the leading elements of \(c\) sequences \((2d_i+S(v_i,1),S(v_i,2)-S(v_i,1),\ldots, S(v_i,|T_i|)-S(v_i,|T_i|-1) )\). Moreover, assume that they satisfy \(S(v_i,1)\geq S(v_i,2)-S(v_i,1)\) and \(S(v_i,x)-S(v_i,x-1)\geq S(v_i,x+1)-S(v_i,x)\). If we define a multiset \(\mathcal{S}\) as

\[ \mathcal{S}_u= \left[\bigcup_{i=1}^c \{2d_i+S(v_i,1),S(v_i,2)-S(v_i,1),\ldots, S(v_i,|T_i|)-S(v_i,|T_i|-1) \}\right]\cup\{0\}, \]

then the elements sorted in descending order, \((z_1,z_2,\ldots,z_{|T_u|})\), coincide with \((S(u,1),S(u,2)-S(u,1),\ldots, S(u,|T_u|)-S(u,|T_u|-1))\). Then, we have \(S(u,1)\geq S(u,2)-S(u,1)\) and \(S(u,x)-S(u,x-1)\geq S(u,x+1)-S(u,x)\) for \(u\) too. Since it automatically holds for \(|T_u|=1\), this property inductively holds always, and thus can be computed like this.

Based on this fact, we can compute it as follows.

When processing a non-leaf vertex, compute \(2d_i+S(v_i,1)\) \((1\leq i\leq c)\) and store the maximum among them to \(S(u,1)\), and store the other \((c-1)\) values and one \(0\) into a multiset \(\mathcal{S} \).

\(S(1,1)\) is the last value stored, and \(S(1,K)\) is \(S(1,1)\) plus the sum of the largest \((K-1)\) elements of \(\mathcal{S}\).

The complexity is \(O(N)\), which is fast enough.

Thus, the problem has been solved.

Sample code in C++:

```
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define MAX_N (int)2e+5
vector<long long>a;
vector<pair<int,ll> >e[MAX_N];
ll dfs(int k,int p){
ll mx=0,tmp;
int sz=e[k].size();
rep(i,sz){
if(e[k][i].first!=p){
tmp=dfs(e[k][i].first,k)+e[k][i].second;
if(tmp>mx){
a.push_back(mx);
mx=tmp;
}
else a.push_back(tmp);
}
}
return mx;
}
int main(void){
int n,u,v,sz;
ll x;
cin>>n;
rep(i,n-1){
cin>>u>>v>>x;
u--,v--;
e[u].push_back({v,x});
e[v].push_back({u,x});
}
a.push_back(dfs(0,-1));
sort(a.begin(),a.end());
x=0;
sz=a.size();
rep(i,n){
x+=a[sz-i-1]*2;
cout<<x<<endl;
}
return 0;
}
```

posted:

last update: