PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Anshul Garg
Tester & Editorialist: Taranpreet Singh
DIFFICULTY
Easy-Medium
PREREQUISITES
Greedy, Exchange argument.
PROBLEM
Given a tree with N nodes numbered from 1 to N with root at node 1, You need to Assign values to nodes satisfying following conditions.
- value of node 1 is X
- All immediate children of a node have pairwise distinct values
- For all nodes having at least one child, the gcd of value of child nodes must be equal to the value of node.
Among all such assignments, find the sum of values of node in the assignment which minimizes the sum of value of nodes.
QUICK EXPLANATION
- For each node, calculate the contribution of the subtree of a node assuming the root of subtree is assigned 1.
- Considering all children of a node, assign 1 to the child with largest contribution, 2 to second largest contribution and so on.
EXPLANATION
Let us make a couple of observations first.
Observation 1: Value of a child node is a multiple of value of its parent node, since gcd of value of children nodes is equal to value of parent node.
In order to minimize sum, if value of parent node is x, it makes sense to assign value to children nodes as multiples of x, say x, 2*x, 3*x \ldots k*x where k is the number of immediate children. This way, gcd of values of immediate children would be equal to the value of node as well.
Now, we need to order the children in some optimal way so as to minimize sum.
Observation 2: For a subtree rooted at node u, if we find an assignment of values to nodes in subtree of u where A_u = 1, We can multiply the values in subtree by A_u to obtain a value assignment without violating any conditions, with the sum of values being multiplied by A_u as well.
Significance of observation 2: This observation allows us to compute the contribution of nodes in subtree of node u, irrespective of value assigned to node u. Hence, we can first compute it’s contribution, and then assign value so as to minimize sum.
Let’s denote the sum of value of nodes in subtree of node u, assuming A_u = 1 by f(u). For leaf nodes, f(u) = 1, since the only node in subtree has value 1.
If u is not a leaf node, assuming it has k children, we can see that each child will be assigned value from 1 to k such that each child gets a distinct value. Let’s assume node u has children a and b. Then f(u) = 1 + min(f(a) + 2*f(b), f(b) + 2*f(a)). We can see that if f(a) < f(b), it makes sense to assign 1 to b and 2 to a.
Formally, to minimize sum, we should assign children values from 1 to k by first ordering children in the non-increasing order of their contribution function. It can be proven using exchange argument that this assignment minimizes sum.
dfs(f, u):
f(u) = 1
list = []
for(v in g[u]):
dfs(f, v)
list.append(f[v])
list.sort(reverse=True)
for i in range(len(list)):
f(u) += (i+1)*list[i]
Finally, after computing f(1), which assumes A_1 = 1, we can multiply value of all nodes by X, effectively multiplying the sum of values by X, to obtain minimum sum assignment with root node having A_1 = X. Hence, X*f(1) is the required sum of values.
What if the values during computation of f(1) overflows?
It won’t happen with long long int. The maximum values we were able to achieve were for tests like star, stars attached at end of binary tree. Even in those cases, the maximum values we were able to achieve were near 10^{11}. Please let me know if you can achieve higher values.
Getting WA on last 1 or 2 files?
Those files were intended to fail some solutions taking MOD, or using int and getting overflow.
TIME COMPLEXITY
The time complexity is O(N*log(N)) per test case.
SOLUTIONS
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
const int mod = 1000000007;
vector<int> adj[500001];
int dfs(int node, int parent) {
multiset<int> s;
for (auto i : adj[node]) {
if (i == parent) continue;
int ans = dfs(i, node);
s.insert(ans);
}
int res = 1, val = 1;
for (auto i = s.rbegin(); i != s.rend(); i++) {
res += (val++) * (*i);
}
return res;
}
void solve() {
int n, x;
cin >> n >> x;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int ans = dfs(1, -1); ans %= mod;
cout << (ans * x) % mod << endl;
for (int i = 1; i <= n; i++) adj[i].clear();
}
signed main() {
fast
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Tester's Solution
import java.util.*;
import java.io.*;
class THOUSES{
//SOLUTION BEGIN
long MOD = (long)1e9+7;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
long X = ni();
int[] from = new int[N-1], to = new int[N-1];
for(int i = 0; i< N-1; i++){
from[i] = ni()-1;
to[i] = ni()-1;
}
int[][] tree = make(N, from, to);
long[] f = new long[N];
dfs(tree, f, 0, -1);
long ans = f[0]%MOD*X%MOD;
pn(ans);
}
void dfs(int[][] g, long[] f, int u, int p){
List<Long> list = new ArrayList<>();
for(int v:g[u]){
if(v == p)continue;
dfs(g, f, v, u);
list.add(f[v]);
}
Collections.sort(list, Collections.reverseOrder());
f[u] = 1;
int mul = 1;
for(long x:list)
f[u] += x * mul++;
}
int[][] make(int N, int[] from, int[] to){
int[] cnt = new int[N];
for(int x:from)cnt[x]++;
for(int x:to)cnt[x]++;
int[][] g = new int[N][];
for(int i = 0; i< N; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< N-1; i++){
g[from[i]][--cnt[from[i]]] = to[i];
g[to[i]][--cnt[to[i]]] = from[i];
}
return g;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new THOUSES().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 