QUERY1206 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: dr_strange_12
Testers: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

DFS, Euler tour of a tree

PROBLEM:

You’re given a rooted tree on N vertices.
For each x = 1, 2, \ldots, N, find the maximum value of \gcd(x, y) across all vertices y such that:

  • y \lt x; and
  • y lies in the subtree of x.

EXPLANATION:

Let’s fix a value g, and try to find all vertices x for which some y with \gcd(x, y) = g and y \lt x exists in the subtree of x.
Well, more specifically, we’ll look for y such that \gcd(x, y) is a multiple of g - that relaxation is often easier to deal with.

Since g is fixed, observe that we only care about x that are multiples of g - that is, x = g, 2g, 3g, \ldots
Then, for x = k\cdot g, all we want to know is whether some smaller multiple of g exists within the subtree of x — if it does, choosing any such smaller multiple gets us a GCD of (a multiple of) g, while if no such vertex exists it’s obviously impossible to do so.

To perform the necessary check quickly, we build an Euler tour of the tree.
Specifically, the Euler tour of a tree has the nice property that v lies in the subtree of u if and only if
\text{in}[u] \leq \text{in}[v] \lt \text{out}[u].

This gives us the following algorithm:

  1. Fix g, the GCD we’re considering.
    Iterate over multiples of g, in order of g, 2g, \ldots.
    Also, maintain a set S that contains the in-times of vertices we’ve seen so far.
  2. When processing vertex x, we only want to check if there exists some previously seen vertex y such that \text{in}[x] \leq \text{in}[y] \lt \text{out}[x].
    If any y satisfies this, certainly the one with \text{in}[y] closest to \text{in}[x] will.
    So, find the smallest element of S that’s \geq \text{in}[x] (using binary search), and check if it satisfies the inequality.
    Then, insert \text{in}[x] into S.

This way, each pair of (g, x) where x is a multiple of g is processed in \mathcal{O}(\log N) time, since we perform one binary search and one set insertion.
There are \left\lfloor \frac{N}{g} \right\rfloor multiples of g till N, so the total number of pairs we check is
\displaystyle\sum_{g=1}^N \left\lfloor \frac{N}{g} \right\rfloor
which is well-known to be \mathcal{O}(N\log N).

This makes the overall complexity \mathcal{O}(N\log^2 N), which is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N\log^2 N) per testcase.

CODE:

Author's code (C++)
/*
   ॐ नमो भगवते वासुदेवाय नमः
   ॐ भूर्भुव: स्व: तत्सवितुर्वरेण्यं भर्गो देवस्य धीमहि धियो यो न: प्रचोदयात्।
*/
// all hail Infront of almighty lord krishna (jai shri krishna ji)
  #include<bits/stdc++.h>
  #ifndef  ONLINE_JUDGE
  #include "debug.h"
  #else
  #define print(...) 1;
  #endif
  using namespace std;
  #define int long long 
  const long long INF =1e18;
  const int N=200000;
  const int mod = 998244353;
  
  template <class T> class ST{
  private: int n;
      const T O = INT_MAX;
      vector<T> seg;
      T op(T x, T y){return min(x, y);}
      void push(int p){seg[p] = op(seg[p << 1], seg[p << 1 | 1]);}
  public: ST(int _n) : n(_n){seg.assign(2 * _n + 2, O);}
      void update(int p, T val){for (seg[p += n] = val, p >>= 1; p; p >>= 1) push(p);}
      T query(int l, int r){
          T ra = O, rb = O;
          for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
              if (l & 1) ra = op(ra, seg[l++]);
              if (r & 1) rb = op(seg[--r], rb);
          }
          return op(ra, rb);
      }
      T query(int p){return query(p, p);}
      void add(int p, T u){update(p, query(p) + u);}
  };
  void Solve()
  {
    int n;
    cin>>n;
    int root;
    cin>>root;
    root--;
    vector<int> adj[n];
    for(int i=0;i<n-1;i++)
    {
      int u,v;
      cin>>u>>v;
      u--;
      v--;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    vector<int>in(n);
    vector<int>out(n);
    int tm=0;
    function<void(int,int)>dfs=[&](int node, int par){
      in[node]=++tm;
      for(auto it:adj[node])
      {
        if(it==par)
        {
          continue;
        }
        dfs(it,node);
      }
      out[node]=tm;
    };
    dfs(root,-1);
    ST<int> seg(n);
    vector<int>ans(n,-1);
    vector<pair<pair<int,int>,int>>a;
    for(int i=1;i<=n;i++)
    {
      for(int j=i;j<=n;j+=i)
      {
        int p=seg.query(in[j-1],out[j-1]);
        if(p<=out[j-1])
        {
          ans[j-1]=max(ans[j-1],i);
        }
        seg.update(in[j-1],out[j-1]);
      }
      for(int j=i;j<=n;j+=i)
      {
        seg.update(in[j-1],INT_MAX);
      }
    }
    for(auto it:ans)
    {
      cout<<it<<" ";
    }
    cout<<"\n";
  }
 
  signed main()
  { 
    
      auto begin = std::chrono::high_resolution_clock::now();
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout<<fixed;
      int t = 1;
       cin >> t;
 
      for(int i = 1; i <= t; i++) 
      {
          // cout << "Case #" << i << ": ";
          Solve();
 
      }
      auto end = std::chrono::high_resolution_clock::now();
      auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
      // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
      return 0;       
  }
Tester's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x) 
#define btz(x) __builtin_ctz(x)
using namespace std;

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
  
int power( int N, int M){
    int power = N, sum = 1;
    if(N == 0) sum = 0;
    while(M > 0){if((M & 1) == 1){sum *= power;}
    power = power * power;M = M >> 1;}
    return sum;
}

const int MX = 1e5+5;
vi adj[MX];
// vi fac[MX];
int st[MX],en[MX];
vector<bool> vis(MX);
int timer;

void dfs(int cur,int par){
    st[cur] = timer++;
    vis[cur] = true;
    for(auto x : adj[cur]){
        if(x == par)continue;
        dfs(x,cur);
    }
    en[cur] = timer;
}
 
void solve()
{
    int n;
    cin >> n;
    assert(n >= 2);
    assert(n <= 1e5);
    int r;
    cin >> r;
    assert(r >= 1);
    assert(r <= n);
    timer = 0;
    rep(i,1,n+1){
        adj[i].clear();
        vis[i] = 0;
    }
    rep(i,0,n-1){
        int u,v;
        cin >> u >> v;
        assert(u >= 1);assert(v >= 1);
        assert(u <= n);assert(v <= n);
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(r,0);
    for(int i = 1;i <= n;i++){
        assert(vis[i]);
    }
    vi ans(n+1,-1);
    for(int i = 1;i <= n;i++){
        set<int> s;
        for(int x = i;x <= n;x += i){
            if(s.size()){
                auto it = s.lb(st[x]);
                if(it != s.end()){
                    int res = (*it);
                    if(res < en[x]){
                        ans[x] = i;
                    }
                }
            }
            s.insert(st[x]);
        }
    }
    rep(i,1,n+1){
        cout << ans[i] << " ";
    }
    cout << "\n";

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
    // for(int i = 1;i < MX;i++){
    //     for(int j = i;j < MX;j += i){
    //         fac[i].pb(j);
    //     }
    // }
    int t;
    cin >> t;
    assert(1 <= t);
    assert(t <= 1e4);
    while(t--)
    solve();
    return 0;
}
Editorialist's code (C++)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, root; cin >> n >> root;
        vector adj(n+1, vector<int>());
        for (int i = 0; i < n-1; ++i) {
            int u, v; cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        vector<int> in(n+1), out(n+1);
        int timer = 0;
        auto dfs = [&] (const auto &self, int u, int p) -> void {
            in[u] = timer++;
            for (int v : adj[u]) {
                if (v == p) continue;
                self(self, v, u);
            }
            out[u] = timer;
        };
        dfs(dfs, root, 0);
        
        vector<int> ans(n+1, -1);
        for (int x = 1; x <= n; ++x) {
            set<array<int, 2>> st;
            for (int u = x; u <= n; u += x) {
                auto it = st.lower_bound({in[u], u});
                if (it != end(st)) {
                    auto [tm, v] = *it;
                    if (out[v] <= out[u]) ans[u] = x;
                }
                st.insert({in[u], u});
            }
        }
        ans.erase(ans.begin());
        for (int x : ans) cout << x << ' ';
        cout << '\n';
    }
}

https://www.codechef.com/viewsolution/1076240640
here same my approach without segtree

The test case are too weak
I’ve seen a few ACs which fails the following simple case
here G[45] should be 15, but many solutions give 1

1
45 15
15 45
15 1
15 2
15 3
15 4
15 5
15 6
15 7
15 8
15 9
15 10
15 11
15 12
15 13
15 14
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
15 25
15 26
15 27
15 28
15 29
15 31
15 32
15 33
15 34
15 35
15 36
15 37
15 38
15 39
15 40
15 41
15 42
15 43
15 44
45 30

https://www.codechef.com/viewsolution/1076687200
I followed the same approach as you. I am getting WA. can you check it?