PATHETIC - Editorial

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. :scream:

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

But 100! is greater than the constraint for each node value.

1 Like

amazing problem!!!

Suppose the following case

        O-#
       /
R-O-#-O
       \
        O-#

The #'s are at depths 3 and 6 and therefore the only ones that are divisible by 3. Now notice that that at the branch there is a sequence of 3 O’s who’se product is not divisible by 3

1 Like

Okay…i see. :+1:

The logic is totally correct bhai
just those authors constraint will meddle around.

but theres no loophole in your logic,

1 Like

And what if we repeat the process for every leaf node?

Then I think the values could become too large. But please try it as I’m not entirely sure.

It doesn’t matter. Take any node as “root”. Try on pen-paper taking other root than “0” (0-indexing) or “1” (1-indexing). You will get a valid solution.

1 Like

This indeed works, the maximum sequence of nodes that is not divisible by p would be p-2 which satisfies the conditions. I am curious if the setter (@sjshohag ) was not aware of this solution, as it would imply that N could be increased to around 10^7.

How to choose p1 and p2 anyone? I tried adding alternate primes in each set but it exceeds 2e18

@rajarshi_basu This should be explained in the editorial. Both the setter and tester use a “greedy” approach that might not be entirely obvious

3 Likes