I just upsolved it now. I used a similar approach, I set the value of node at level “l” as “l*(2l-1)”. (Level of Root = 1) @rohitkv77
Brilliant editorial !
5 Likes
I tried this but got TLE.
Can you check were am I going wrong?
https://www.codechef.com/viewsolution/35809478
I have an alternative solution.
Root the tree. Then multiply the prime number p to every node at depth \frac{p}{2}, \frac{2p}{2}, \frac{3 p}{2}, \dots.
The ideas behind it is: a path of lenght l has at least an upwards path of lenght \frac{l}{2}, and therefore it will meet every prime factor of l, even if l is prime itself.
This way every node of the tree gets a value assigned less then 4 \cdot 10^{10}. And I assume you can make this bound even smaller…
Solution: CodeChef: Practical coding for everyone
Edit: Nevermind. There are much better solutions out there.
7 Likes
p1=1816798556036292277
p2=1269027849171992910
Allot p1 to all odd depth nodes, p2 to all even depth nodes.
(Logic- generated all prime numbers less than 100, then made two products which are <=2e18)
3 Likes
Imagine having all the ideas, splitting the primes into two buckets and even the bipartite bit, but missing one prime. I was dealing with 24 primes for almost half an hour and had no idea what was going wrong. I googled and found that there are 25 primes and managed to solve it. Note to self: Don’t do list initialization of primes by yourself. Please use a sieve
6 Likes
can anyone plz tell me what is wrong with my submission
logic- devide all the prime to x,y such that x<=2e18 and y<=2e18 than allot x and y alternatively from any node according to hieght ie nodes at the same height will get same values i.e eithe x or y
Bhai credit to de 
1 Like
I thought for this approach but unable to implement…
1 Like
Well it has sample time complexity but maybe 1.3-2 times slower because of vectors and stuff like that.
Mine passes in 0.80 secs.
2 Likes
Mine in 0.00 ,but it take a lot of time , for next problem I had no time left 
1 Like
A much easier solution
vll val;
vvi g;
void dfs(int node, int par = -1, ll pro = 1) {
val[node] = 2 * pro * (2 * pro + 1);
for (auto v: g[node]) {
if (v != par) {
dfs(v, node, pro + 1);
}
}
}
void solveOne(istream& cin, ostream& cout) {
int n;
cin >> n;
g = vvi(n);
val.clear();
val.resize(n, 1);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(0);
for (int i = 0; i < n; ++i) {
cout << val[i] << " ";
}
cout << '\n';
}
6 Likes
Hey @vol_8, how did you have selected 0 as root?
If any1 can explain, why 0 is always be a root?
Or is it a week test case?
I guess that’s the reason they named it path-ETIC. 
sorry u r not tasty
1 Like
A tasty problem from chefs floura & fauna
what’s wrong in my solution ?
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define endl '\n' #ifdef rd #define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__) template<typename Arg1> void __f(const char* name, Arg1&& arg1) { cout<<name<<" : "<<arg1<<endl; } template<typename Arg1, typename ... Args> void __f(const char* names, Arg1&& arg1, Args&&... args) { const char* comma=strchr(names+1,','); cout.write(names,comma-names)<<" : "<<arg1<<" | "; __f(comma+1,args...); } #else #define trace(...) #endif #define pb push_back #define fi first #define se second #define mkp make_pair //#define int long long typedef long long ll; typedef long double f80; //#define double long double #define pii pair<int,int> #define pll pair<ll,ll> #define sz(x) ((long long)x.size()) #define fr(a,b,c) for(int a=b; a<=c; a++) #define frdec(a,b,c) for(int a=b; a>=c; a--) #define rep(a,b,c) for(int a=b; a<c; a++) #define trav(a,x) for(auto &a:x) #define all(con) con.begin(),con.end() const ll infl=2e18; const int infi=2e9; const int mod=1e9+7; typedef vector<int> vi; mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count()); auto clk=clock(); int rng(int lim) { uniform_int_distribution<int> uid(0,lim-1); return uid(rang); } template<class t1, class t2, class t3> t1 fast_expo(t2 x, t3 p) { if(p == 0) return 1; t1 r = fast_expo(x,p/2); if(p%2 != 0) return r * r * x; return r * r; } // ===================LOGIC===================== int n; unordered_map<int, vector<int>> t; vector<ll> assignment; vector<int> spf(101); void sieve() { for(int i = 1; i <= 100; i++) spf[i] = i; for(int i = 2; i * i <= n; i++) { if(spf[i] == i) { for(int j = i * i; j <= n; j += i) { if(spf[j] == j) spf[j] = i; } } } } vector<int> getFactors(int n) { vector<int> fact; while(n != 1) { fact.push_back(spf[n]); n = n / spf[n]; } return fact; } void dfs(int u, int p, int S, ll pdt) { auto fact = getFactors(S); pdt = pdt * assignment[u]; ll toBeMult = 1; auto x = pdt; for(auto f : fact) { if(x % f != 0) toBeMult *= f; else x = x / f; } pdt *= toBeMult; assignment[u] *= toBeMult; for(auto v : t[u]) { if(v == p) continue; dfs(v, u, S+1, pdt); } } void reset() { n = 0; t.clear(); assignment.clear(); } void read() { cin >> n; for(int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; t[u].pb(v); t[v].pb(u); } assignment.assign(n+1, 1); } void solve() { read(); for(int i = 1; i <= n; i++) { dfs(i, -1, 1, assignment[i]); } for(int i = 1; i <= n; i++) cout << assignment[i] << " "; cout << "\n"; } // ===================LOGIC===================== signed main() { ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count()); cout<<fixed<<setprecision(10); int t=1; cin>>t; sieve(); while(t--) { reset(); solve(); } return 0; }
In the constraints
1≤N≤100 ,
so its bit convenient to select 0 as the root;
with no interference of N
Can anyone explain this?
Why assigning depths to particular node from any leaf node would not work?
What if i allot every node value of n! and print it.
For calculating factorial of large numbers like 100 you can refer to Find the Factorial of a large number - GeeksforGeeks