rds_98
July 19, 2020, 8:41pm
23
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?
unsung_heroes:
1269027849171992910
I guess that’s the reason they named it path-ETIC.
A tasty problem from chefs floura & fauna
hv7214
July 20, 2020, 4:52am
32
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
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
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.
vok_8
July 20, 2020, 5:58am
43
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