#724452 (C++17) No.1787 Do Use Dynamic Tree

• 問題: No.1787 Do Use Dynamic Tree
• ユーザー: 👑 Nachia
• 提出日時: 2021-12-16 21:29:26
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,590 ms / 10,000 ms
• コード長: 11,142 bytes
• コンパイル時間: 1,942 ms
• コンパイル使用メモリ: 121,896 KB
• 実行使用メモリ: 55,068 KB
• 最終ジャッジ日時: 2023-10-11 20:45:09
• 合計ジャッジ時間: 38,920 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,356 KB
testcase_01	AC	2 ms; 4,352 KB
testcase_02	AC	2 ms; 4,352 KB
testcase_03	AC	2 ms; 4,352 KB
testcase_04	AC	2 ms; 4,352 KB
testcase_05	AC	1 ms; 4,348 KB
testcase_06	AC	2 ms; 4,352 KB
testcase_07	AC	1 ms; 4,352 KB
testcase_08	AC	2 ms; 4,348 KB
testcase_09	AC	2 ms; 4,356 KB
testcase_10	AC	2 ms; 4,352 KB
testcase_11	AC	2 ms; 4,352 KB
testcase_12	AC	6 ms; 4,348 KB
testcase_13	AC	6 ms; 4,348 KB
testcase_14	AC	8 ms; 4,352 KB
testcase_15	AC	6 ms; 4,356 KB
testcase_16	AC	7 ms; 4,352 KB
testcase_17	AC	7 ms; 4,348 KB
testcase_18	AC	6 ms; 4,352 KB
testcase_19	AC	6 ms; 4,352 KB
testcase_20	AC	5 ms; 4,352 KB
testcase_21	AC	7 ms; 4,352 KB
testcase_22	AC	2,031 ms; 34,528 KB
testcase_23	AC	1,503 ms; 49,036 KB
testcase_24	AC	1,519 ms; 29,976 KB
testcase_25	AC	2,571 ms; 52,180 KB
testcase_26	AC	2,566 ms; 52,300 KB
testcase_27	AC	2,590 ms; 52,192 KB
testcase_28	AC	886 ms; 55,048 KB
testcase_29	AC	879 ms; 54,704 KB
testcase_30	AC	873 ms; 55,068 KB
testcase_31	AC	1,418 ms; 49,308 KB
testcase_32	AC	1,683 ms; 49,348 KB
testcase_33	AC	2,194 ms; 49,984 KB
testcase_34	AC	1,044 ms; 49,316 KB
testcase_35	AC	1,535 ms; 49,352 KB
testcase_36	AC	2,120 ms; 50,052 KB
testcase_37	AC	1,906 ms; 52,076 KB
testcase_38	AC	1,986 ms; 51,832 KB
testcase_39	AC	1,989 ms; 51,748 KB

ソースコード

#include <atcoder/segtree>




#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct heavy_light_decomposition{
private:

  int N;
  vector<int> P;
  vector<int> PP;
  vector<int> PD;
  vector<int> D;
  vector<int> I;

  vector<int> rangeL;
  vector<int> rangeR;

public:

  heavy_light_decomposition(const vector<vector<int>>& E = {{}}){
    N = E.size();
    P.assign(N, -1);
    I = {0};
    I.reserve(N);
    for(int i=0; i<I.size(); i++){
      int p = I[i];
      for(int e : E[p]) if(P[p] != e){
        I.push_back(e);
        P[e] = p;
      }
    }
    vector<int> Z(N, 1);
    vector<int> nx(N, -1);
    PP.resize(N);
    for(int i=0; i<N; i++) PP[i] = i;
    for(int i=N-1; i>=1; i--){
      int p = I[i];
      Z[P[p]] += Z[p];
      if(nx[P[p]] == -1) nx[P[p]] = p;
      if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p;
    }

    for(int p : I) if(nx[p] != -1) PP[nx[p]] = p;

    PD.assign(N,N);
    PD[0] = 0;
    D.assign(N,0);
    for(int p : I) if(p != 0){
      PP[p] = PP[PP[p]];
      PD[p] = min(PD[PP[p]], PD[P[p]]+1);
      D[p] = D[P[p]]+1;
    }
    
    rangeL.assign(N,0);
    rangeR.assign(N,0);
    vector<int> dfs;
    dfs.push_back(0);
    while(dfs.size()){
      int p = dfs.back();
      rangeR[p] = rangeL[p] + Z[p];
      int ir = rangeR[p];
      dfs.pop_back();
      for(int e : E[p]) if(P[p] != e) if(e != nx[p]){
        rangeL[e] = (ir -= Z[e]);
        dfs.push_back(e);
      }
      if(nx[p] != -1){
        rangeL[nx[p]] = rangeL[p] + 1;
        dfs.push_back(nx[p]);
      }
    }

    I.resize(N);
    for(int i=0; i<N; i++) I[rangeL[i]] = i;
  }

  int depth(int p) const {
    return D[p];
  }

  int lca(int u, int v) const {
    if(PD[u] < PD[v]) swap(u, v);
    while(PD[u] > PD[v]) u = P[PP[u]];
    while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; }
    return (D[u] > D[v]) ? v : u;
  }

  int dist(int u, int v) const {
    return depth(u) + depth(v) - depth(lca(u,v)) * 2;
  }

  vector<pair<int,int>> path(int r, int c, bool include_root = true, bool reverse_path = false) const {
    vector<pair<int,int>> res;
    while(PD[r] < PD[c]){
      res.push_back({ rangeL[PP[c]], rangeL[c]+1 });
      c = P[PP[c]];
    }
    if(PP[r] != PP[c]) return {};
    if(D[r] > D[c]) return {};
    res.push_back({ rangeL[r], rangeL[c]+1 });
    if(!include_root){
      res.back().first++;
      if(res.back().first == res.back().second) res.pop_back();
    }
    if(!reverse_path) reverse(res.begin(),res.end());
    return res;
  }

  const vector<int>& idxs() const {
    return rangeL;
  }
  const vector<int>& invidxs() const {
    return I;
  }

  int meet(int x, int y, int z) const {
    return lca(x,y) ^ lca(y,z) ^ lca(x,z);
  }

  int jump(int from, int to, int d) const {
    int g = lca(from,to);
    int dist0 = D[from] - D[g] * 2 + D[to];
    if(dist0 > d) return -1;
    int p = from;
    if(D[from] - D[g] > d){ p = to; d = dist0 - d; }
    while(D[p] - D[PP[p]] > d){
      d -= D[p] - D[PP[p]] + 1;
      p = P[PP[p]];
    }
    return I[rangeL[p] - d];
  }
  
  int heavy_path_child(int p){
    int ip = rangeL[p];
    if(ip == N-1) return -1;
    int cand = I[ip + 1];
    if(PP[cand] != PP[p]) return -1;
    return cand;
  }
  
  int parent(int p){ return P[p]; }
  
};




#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

namespace ruq {
    map<int,int> rq;
    void init(){
        rq[-1] = 0;
    }
    int query(int p){
        auto i = rq.upper_bound(p);
        i--;
        return i->second;
    }
    void apply(int l, int r, int updval){
        if(l >= r) return;
        int lastval = query(l);
        auto i = rq.lower_bound(l);
        while(true){
            if(i == rq.end()) break;
            if(r < i->first) break;
            lastval = i->second;
            i = rq.erase(i);
        }
        rq.insert(make_pair(l, updval));
        rq.insert(make_pair(r, lastval));
    }
}


int N;
vector<int> A;
vector<vector<int>> E;
heavy_light_decomposition hld;
vector<set<pair<int,int>, greater<pair<int,int>>>> children;
vector<int> maxchild;
vector<int> ismaxchild;

namespace all_is_good_query{
    using S = int;
    S op(S l, S r){ return l & r; }
    S e(){ return 1; }
    using rq = atcoder::segtree<S,op,e>;
    bool check(S x){ return x; }
}


all_is_good_query::rq isparentparentmax_rq;
all_is_good_query::rq ismaxchild_rq;

int is_parent_max(int p){
    if(p == 0) return 0;
    if(maxchild[p] < 0) return 1;
    return (A[hld.parent(p)] > A[maxchild[p]]) ? 1 : 0;
}

int is_parent_parent_max(int p){
    if(hld.depth(p) < 2) return 0;
    int pp = hld.parent(p);
    int ppp = hld.parent(pp);
    if(children[pp].size() <= 1) return 1;
    if(maxchild[pp] != p) return (A[ppp] > A[maxchild[pp]]) ? 1 : 0;
    auto i = children[pp].begin(); i++;
    return (A[ppp] > A[i->second]) ? 1 : 0;
}

int solve_parentmax2(int x){
    if(x == 0) return x;
    if(is_parent_max(x) == 0) return x;
    while(is_parent_parent_max(x)) x = hld.parent(x);
    if(x != 0) x = hld.parent(x);
    return x;
}

int solve_parentmax(int x){
    if(x == 0) return x;
    if(is_parent_max(x) == 0) return x;
    auto path = hld.path(0,x);
    while(!path.empty()){
        auto p = path.back();
        path.pop_back();
        int l = isparentparentmax_rq.min_left(p.second, all_is_good_query::check);
        l = min(max(l, p.first + 2), p.second);
        if(p.first + 2 < l){ return hld.invidxs()[l-2]; }
        while(l != p.first){
            l--;
            int pathp = hld.invidxs()[l];
            if(!is_parent_parent_max(pathp)) return hld.parent(pathp);
        }
    }
    return 0;
}

int solve_maxchild(int x){
    auto path = hld.path(0,x);
    while(!path.empty()){
        auto p = path.back();
        path.pop_back();
        int l = ismaxchild_rq.min_left(p.second, all_is_good_query::check);
        if(p.first + 1 < l){ return hld.invidxs()[l-1]; }
        int pathp = hld.invidxs()[p.first];
        if(!ismaxchild[pathp]) return pathp;
    }
    return 0;
}
int solve_maxchild2(int c){
    while(ismaxchild[c]) c = hld.parent(c);
    return c;
}


vector<int> dp;

void set_A(int p, int a){
    int heavy_child = hld.heavy_path_child(p);
    int parent = hld.parent(p);
    int heavy_child2 = -1;
    if(heavy_child != -1) heavy_child2 = hld.heavy_path_child(heavy_child);
    
    if(parent != -1){
        children[parent].erase(make_pair(A[p], p));
    }
    
    A[p] = a;
    
    if(parent != -1){
        children[parent].insert(make_pair(A[p], p));
        ismaxchild[maxchild[parent]] = 0;
        ismaxchild_rq.set(hld.idxs()[maxchild[parent]], 0);
        maxchild[parent] = children[parent].begin() -> second;
        ismaxchild[maxchild[parent]] = 1;
        ismaxchild_rq.set(hld.idxs()[maxchild[parent]], 1);

        int updv = ruq::query(hld.idxs()[maxchild[parent]]);
        int updr = solve_maxchild(parent);
        for(auto path : hld.path(updr, parent)) ruq::apply(path.first, path.second, updv);
        
        int evil_heavy_child = hld.heavy_path_child(parent);
        if(evil_heavy_child != -1) isparentparentmax_rq.set(hld.idxs()[evil_heavy_child], is_parent_parent_max(evil_heavy_child));
    }

    if(heavy_child != -1) isparentparentmax_rq.set(hld.idxs()[heavy_child], is_parent_parent_max(heavy_child));
    if(heavy_child2 != -1) isparentparentmax_rq.set(hld.idxs()[heavy_child2], is_parent_parent_max(heavy_child2));
    isparentparentmax_rq.set(hld.idxs()[p], is_parent_parent_max(p));
    /*
    cout << "A updated : p = " << p << endl;
    cout << "    heavy_child = " << heavy_child << endl;
    cout << "    heavy_child2 = " << heavy_child << endl;
    cout << "    A = ["; for(auto a : A) cout << " " << a; cout << " ]" << endl;
    cout << "    maxchild = ["; for(auto a : maxchild) cout << " " << a; cout << " ]" << endl;
    cout << "    ismaxchild = ["; for(auto a : ismaxchild) cout << " " << a; cout << " ]" << endl;
    cout << "    isparentmax = ["; rep(i,N) cout << " " << is_parent_max(i); cout << " ]" << endl;
    cout << "    isparentparentmax = ["; rep(i,N) cout << " " << isparentparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl;
    cout << "    isparentparentmax2= ["; rep(i,N) cout << " " << is_parent_parent_max(i); cout << " ]" << endl;
    cout << "    query = ["; rep(i,N) cout << " " << ruq::query(hld.idxs()[i]); cout << " ]" << endl;
    */
}


int query(int u, int v){
    int au = A[u];
    int av = A[v];
    set_A(u, av);
    set_A(v, au);
    int g = solve_parentmax(u);
    if(u != g){
        if(children[g].size() <= 1) return g;
        else if(hld.lca(u, maxchild[g]) == maxchild[g]){
            auto i = children[g].begin();
            i++;
            g = i -> second;
        }
    }
    g = ruq::query(hld.idxs()[g]);
    return g;
}


int main(void){
    cin >> N;
    A.resize(N);
    rep(i,N) A[i] = i;
    E.resize(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    
    hld = heavy_light_decomposition(E);
    E.clear();
    E.resize(N);
    children.resize(N);
    
    for(int i=1; i<N; i++){
        E[hld.parent(i)].push_back(i);
        children[hld.parent(i)].insert(make_pair(A[i],i));
    }
    
    maxchild.assign(N,-1);
    rep(i,N) if(!children[i].empty()) maxchild[i] = children[i].begin() -> second;
    ismaxchild.assign(N,0);
    for(int i=1; i<N; i++) ismaxchild[i] = (maxchild[hld.parent(i)] == i) ? 1 : 0;
    
    isparentparentmax_rq = all_is_good_query::rq(N);
    rep(i,N) isparentparentmax_rq.set(hld.idxs()[i], is_parent_parent_max(i));
    ismaxchild_rq = all_is_good_query::rq(N);
    rep(i,N) ismaxchild_rq.set(hld.idxs()[i], ismaxchild[i]);
    
    int prevans = 0;
    int Q; cin >> Q;

    ruq::init();

    {
        //vector<int> dp(N);
        dp.resize(N);
        rep(i,N) dp[i] = i;
        for(int i=N-1; i>=0; i--){
            int p = hld.invidxs()[i];
            if(children[p].empty()) continue;
            dp[p] = dp[maxchild[p]];
        }
        rep(p,N) ruq::rq[hld.idxs()[p]] = dp[p];
    }
    
    /*
    cout << "initialized " << endl;
    cout << "    ismaxchild = ["; for(auto a : ismaxchild) cout << " " << a; cout << " ]" << endl;
    cout << "    isparentparentmax = ["; rep(i,N) cout << " " << isparentparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl;
    cout << "    heavy child = ["; rep(i,N) cout << " " << hld.heavy_path_child(i) << flush; cout << " ]" << endl;
    cout << "    parent = ["; rep(i,N) cout << " " << hld.parent(i) << flush; cout << " ]" << endl;
    */

    rep(queryid, Q){
        int u,v; cin >> u >> v;
        u = (u+N-1+prevans) % N + 1;
        v = (v+N-1+prevans) % N + 1;
        u--; v--;
        int ans = query(u,v) + 1;
        cout << ans << "\n";
        prevans = ans;
        //rep(i,N) assert(solve_parentmax(i) == solve_parentmax2(i));
    }
    
    return 0;
} 
 
struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;