PROBLEM LINK:
Setter: Ahmad
Tester: Yash Chandnani
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
TreeDP
PROBLEM:
You are given a tree with N vertices (numbered 1 through N) and a sequence of integers A_1, A_2, \ldots, A_N. You may choose an arbitrary permutation p_1, p_2, \ldots, p_N of the integers 1 through N. For each valid i, you should assign the value A_{p_i} to vertex i.
Then, you should choose a vertex of the tree and K-1 times, perform one of the following operations:
- Move forward — move to a vertex which is adjacent to your current vertex. However, you must not move to the vertex in which you were immediately before the previus operation (if it exists).
- Turn around — stay in your current vertex. You may only do this if it is impossible to move forward. Since you do not move in this operation, you may move forward again afterwards.
In this process, you obtain a sequence of vertices v_1, v_2, \ldots, v_K — the initial vertex and the vertices in which you were after each operation. Your score is \sum_{i=1}^K A_{p_{v_i}}. What is the maximum possible value of this score?
Constraints
- 1 \le T \le 1,000
- 2 \le N \le 300,000
- 1 \le K \le 10^9
- 1 \le A_i \le 10^9 for each valid i
- the sum of N over all test cases does not exceed 5 \cdot 10^5
EXPLANATION:
Brief Explanation
- Find the shortest leaf-leaf path, and calculate your answer by placing highest values there.
========================
Observation 1
From the process we can gather that
- We have control over which direction I want to go from a node.
- We can only turn around from a leaf node.
How can we utilise these?
Observation 2
It makes sense that we would want to use the larger numbers multiple number of times right?
Reminder
We can assign values to nodes as we wish!
Observation 3
Oscillating on the shortest Leaf-Leaf path is the best case scenario. What do I mean by a Leaf-Leaf path? A path that starts in some leaf, and ends in some other leaf. How do I find such a path? Use Dynamic Programming on Trees. Try to maintain longest and second longest path inside subtree for every node. For more details look inside the DFS function of tester’s code.
Excercise for reader
This is however not enough. You also need to figure out the details on which node to start your journey at, and in which direction. I will leave this for you to find out.
hint: if you start towards the end, then you can visit the starting place more than once even if k is small, by bouncing off the end.
Details 00f
- Let the length of path be n, with nodes numbered from 0,1,2… n-1. Now, just imagine that you start at node x and you want to go towards decreasing node labels. Its always best to choose x = \lfloor \frac{k-1}{2} \rfloor . Think how you would like to arrange your values now. Note that it is always best to put values so that the higher values are repeated twice. Think about the edge case when K is odd. One of the values wont be repeated.
- This wont work when K \geq 2n right? Well…. there you would just oscillate the whole length multiple times before you get K \le 2n, in which case you could again use the above logic.
SOLUTIONS:
Tester’s Code
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
ll a[300009];
int h1[300009],h2[300009];
int z ;
vector<vi> g;
void dfs(int u,int p){
h1[u]=h2[u]=3e5+9;
if(sz(g[u])==1) h1[u]=0;
trav(i,g[u]){
if(i!=p) {
dfs(i,u);
if(h1[i]+1<h1[u]) {
h2[u]=h1[u];
h1[u]=h1[i]+1;
}
else if(h1[i]+1<h2[u]) h2[u]=h1[i]+1;
}
}
z=min(z,h1[u]+h2[u]);
}
ll sum,sumk;
void solve(){
int n=readIntSp(1,3e5),k=readIntLn(1,1e9);
sum+=n,sumk+=k;
assert(n>=2&&n<=300000);
assert(k>=1&&k<=1000000000);
g.clear();
g.resize(n+1);
rep(i,n) {
if(i<n-1) a[i]=readIntSp(1,1e9);
else a[i]=readIntLn(1,1e9);
assert(a[i]>=1&&a[i]<=1000000000);
}
sort(a,a+n);
rep(i,n-1){
int u=readIntSp(1,n),v=readIntLn(1,n);
assert(u!=v);
g[u].pb(v);
g[v].pb(u);
}
z=n;
dfs(1,0);
z++;
ll ans = 0;
repD(i,n-1,n-z){
ll cnt = (k/(2*z))*2;
if(k%(2*z)==2){
if(i>=n-2) cnt++;
}
else{
if(i>=n-(k%(2*z)/2)) cnt+=2;
else if(i==n-(k%(2*z)/2)-1&&(k%(2*z))%2==1) cnt++;
}ans+=a[i]*cnt;
}
cout<<ans<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n=readIntLn(1,1000);
assert(n>=1&&n<=1000);
rep(i,n) solve();
assert(sum<=5e5);
return 0;
}
