PRT2 - Editorial

PROBLEM LINK:

Contest

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;
}
4 Likes

DP on trees is not required I think.
We can use multi-source BFS from each leaf and find the smallest Leaf-Leaf path.

3 Likes

Figuring out since hours now.
https://www.codechef.com/viewsolution/36011806
Can you/anyone please help me in debugging ?

Hey, I used same logic as you. code
Brief reading suggest possible error in bfs or handling of k%(2*l)>2 case. You can use this to match maybe.

1 Like

I will add this in a couple of days maybe. xD
Try till then.

PS: I personally like editorials where not everything is mentioned, but enough is given so that I can think. So I am trying it out this time. However, I will give out the details after a couple of days.

2 Likes

lol I know the logic I think. Couldn’t find any counter case or bug in my code.

Thanks.
what is L here ?
min dist b/w leaves?

yeah. min leaf-leaf distance

1 Like

Please tell a bit more about this…

Instead of one root. You will have multiple root nodes.
Add all of them (leaves) to a queue. And the just normal BFS. Visit all unvisited neighbours.
Whenever we can reach an already visited node we will stop BFS and we will get the min distance b/w any two sources ( i.e leaves).

4 Likes

Why isn’t full editorial uploaded, i already have done till observation 3, main is the node from where to start where i am getting the wrong answer and came to editorials to find my mistake and turns out that part is missing

welcome to the group XD

1 Like

Instead of looking at it like “which node to start from” imagine it like this:

You have a path from 1 leaf to another, and an integer k which denotes the number of possible operations.

Create a function f(n,k) which returns the answer for a path with n nodes with k being k as defined in the problem statement.

Deal with 4 cases first.

If k is 0, return 0. If k is 1, return the maximum element in a. If k is 2 return the maximum element + the second largest element. If k<2*n and k>0, repeatedly do the following:

if k>=2, add 2*the maximum value we can assign and then decrease k by 2, and remove that value from the array of possible values. If k=1, add the maximum value in the array once and break.

This works because we can always visit x nodes 2*x times if we “bounce” off the leaf node.

Then return this answer.

Now for k>=2*n, first notice that in a path from a node -> leaf -> next leaf -> back to the node, we visit each node twice. Hence the answer for this is (2* (floor(k/(2*n))* (the sum of the n maximum values)) + f(n,k%2n)

3 Likes

check this code: https://www.codechef.com/viewsolution/36025380
i am doing exactly same but still its showing correct for one subtask only.
plzz see if there is any error.

Try this TC:
1
9 20
1 2 3 4 5 6 7 8 9
1 2
2 3
3 4
5 4
6 4
6 7
8 7
8 9
Your answer: 138
Correct answer:140

thanks for the case
got my error :slight_smile:

Try including some testcases, a lot of time some testcases help in understanding the problem clearly.

Your bfs always gives answer as 2. Check whether the visited node is a parent of the current node as well.

1 Like

updated editorial.

Ohh bro. Thanks a lot. That makes sense.
Now I got a lesson. “Never trust any code written by anyone”
I skipped checking for different trees. I thought it’s simple BFS so how can it be incorrect.
Thanks a lot ! :grinning:
And guess what. Most of the trees had length = 3 ( two edges)
And I was always using length=3