結果

問題 No.1787 Do Use Dynamic Tree
ユーザー HIR180HIR180
提出日時 2021-12-16 02:18:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,573 ms / 10,000 ms
コード長 14,457 bytes
コンパイル時間 4,427 ms
コンパイル使用メモリ 232,184 KB
実行使用メモリ 167,808 KB
最終ジャッジ日時 2024-07-26 11:54:15
合計ジャッジ時間 30,269 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
46,080 KB
testcase_01 AC 33 ms
45,952 KB
testcase_02 AC 35 ms
46,080 KB
testcase_03 AC 34 ms
46,080 KB
testcase_04 AC 34 ms
45,952 KB
testcase_05 AC 34 ms
45,952 KB
testcase_06 AC 34 ms
45,952 KB
testcase_07 AC 34 ms
46,080 KB
testcase_08 AC 35 ms
46,080 KB
testcase_09 AC 35 ms
46,080 KB
testcase_10 AC 35 ms
45,952 KB
testcase_11 AC 34 ms
45,952 KB
testcase_12 AC 37 ms
46,336 KB
testcase_13 AC 42 ms
46,336 KB
testcase_14 AC 39 ms
46,464 KB
testcase_15 AC 41 ms
46,464 KB
testcase_16 AC 40 ms
46,464 KB
testcase_17 AC 40 ms
46,208 KB
testcase_18 AC 41 ms
46,592 KB
testcase_19 AC 40 ms
46,336 KB
testcase_20 AC 41 ms
46,464 KB
testcase_21 AC 42 ms
46,464 KB
testcase_22 AC 1,118 ms
118,912 KB
testcase_23 AC 1,011 ms
151,168 KB
testcase_24 AC 912 ms
108,672 KB
testcase_25 AC 1,536 ms
159,360 KB
testcase_26 AC 1,573 ms
159,488 KB
testcase_27 AC 1,516 ms
159,232 KB
testcase_28 AC 1,401 ms
165,888 KB
testcase_29 AC 1,402 ms
165,760 KB
testcase_30 AC 1,411 ms
165,888 KB
testcase_31 AC 689 ms
164,668 KB
testcase_32 AC 804 ms
164,736 KB
testcase_33 AC 880 ms
165,632 KB
testcase_34 AC 518 ms
164,672 KB
testcase_35 AC 755 ms
164,736 KB
testcase_36 AC 884 ms
165,504 KB
testcase_37 AC 1,209 ms
166,528 KB
testcase_38 AC 1,236 ms
167,808 KB
testcase_39 AC 1,217 ms
165,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
#define int long long
//#define L __int128
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define a first
#define b second
#define fi first
#define sc second
#define rng(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
#define si(x) int(x.size())
 
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
 
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
 
template<class t> using vc=vector<t>;
 
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.fi<<","<<p.sc<<"}";
}
 
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
 
 //https://codeforces.com/blog/entry/62393
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	
	size_t operator()(pair<int,int> x)const{
		return operator()(uint64_t(x.first)<<32|x.second);
	}
};
//unordered_set -> dtype, null_type
//unordered_map -> dtype(key), dtype(value)
using namespace __gnu_pbds;
template<class t,class u>
using hash_table=gp_hash_table<t,u,custom_hash>;

template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 998244353;
//const ll mod = 1000000007;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
#define _sz 1
ll F[_sz],R[_sz];
void make(){
	F[0] = 1;
	for(int i=1;i<_sz;i++) F[i] = F[i-1]*i%mod;
	R[_sz-1] = modpow(F[_sz-1], mod-2);
	for(int i=_sz-2;i>=0;i--) R[i] = R[i+1] * (i+1) % mod;
}
ll C(int a,int b){
	if(b < 0 || a < b) return 0;
	return F[a]*R[b]%mod*R[a-b]%mod;
}

#define szz 200005
int n;
vector<int>edge[szz];
int up[20][szz],dep[szz];
int cnt[szz];
int hld_cmp[szz],hld_num[szz],hld_sz[szz];
int in[szz],out[szz],rev[szz],nxt;
struct dbling{
	bool ready = 0;
	void dfs(int v,int u,int d){
		up[0][v] = u; dep[v] = d;
		cnt[v] = 1;
		P p = mp(0, 0);
		rep(i,edge[v].size()){
			if(edge[v][i] == u) continue;
			dfs(edge[v][i], v, d+1);
			p = max(p,mp(cnt[edge[v][i]],i));
			cnt[v] += cnt[edge[v][i]];
		}
		swap(edge[v][0],edge[v][p.sc]);
	}
	void make_hld(int v,int u,int up,int id){
		hld_cmp[v] = up;
		hld_num[v] = id;
		hld_sz[up] = max(hld_sz[up],id);
		in[v]=nxt; rev[nxt] = v; nxt++;
		for(int i=0;i<edge[v].size();i++){
			if(edge[v][i] == u) continue;
			if(i == 0){
				make_hld(edge[v][i],v,up,id+1);
			}
			else{
				make_hld(edge[v][i],v,edge[v][i],1);
			}
		}
		out[v] = nxt-1;
	}
	void prepare(){
	    dfs(1,-1,0);
		rep(j,19){
			rep(i,szz){
				if(up[j][i] == -1) up[j+1][i] = up[j][i];
				else up[j+1][i] = up[j][up[j][i]];
			}
		}
		make_hld(1, -1, 1, 1);
		ready = 1;
	}
	int get(int a,int b){
		if(dep[a] > dep[b]) swap(a,b);
		int d = dep[b]-dep[a];
		rep(i,20){
			if(((d>>i)&1)) b = up[i][b];
		}
		if(a == b) return a;
		for(int i=19;i>=0;i--){
			if(up[i][a] != up[i][b]){
				a = up[i][a];
				b = up[i][b];
			}
		}
		return up[0][a];
	}
	int dist(int a,int b){
		int c = get(a,b);
		return dep[a]+dep[b]-2*dep[c];
	}
	int dist(int a,int b,int c){
		//assuming c is lca of (a,b)
		return dep[a]+dep[b]-2*dep[c];
	}
	int go_up(int v,int a){
	    if(dep[v] < a) return -1;
	    rep(i,20) if(((a>>i)&1)) v = up[i][v];
	    return v;
	}
	//a ---- b
	//と並べたときのx番目 (1-indexed)
	//存在しない場合は-1を返す
	//verified : opencup warsaw i
	int v_on_path(int a,int b,int x){
		int c = get(a,b);
		int d = dist(a,b,c);
		if(x <= 0 || x > d+1) return -1;
		if(x <= dep[a]-dep[c]+1){
			return go_up(a, x-1);
		}
		else{
			x = d+2-x;
			return go_up(b, x-1);
		}
	}
}kaede;

int ran[szz], beg[szz], upp[szz], val[szz];
struct node{
  node *l, *r, *p;
  int id;
  node(int i) : l(0), r(0), p(0), id(i) {}
};

inline bool is_root(node *n){
  return n -> p == NULL || n -> p -> l != n && n -> p -> r != n;
}

inline bool left(node *n){
  return n == n -> p -> l;
}

//遅延評価
inline void push(node *n){
}

//値の再計算
inline void update(node *n){
  //最初に遅延評価
  push(n);
}

inline void connect(node *n, node *p, bool l){
  (l ? p -> l : p -> r) = n;
  if(n) n -> p = p;
}

//rotateが呼ばれる前には関与しているノードの遅延評価をする必要がある
inline void rotate(node *n){
  node *p = n -> p, *g = p -> p;
  bool l = left(n);
  connect(l ? n -> r : n -> l, p, l);
  if(!is_root(p)) connect(n, g, left(p));
  else n -> p = g;
  connect(p, n, !l);
  update(p), update(n);
}

inline void splay(node *n){
  while(!is_root(n)){
    node *p = n -> p, *g = p -> p;
    //関与する頂点群の遅延評価をする
    if(!is_root(p)) push(g);
    push(p), push(n);
    if(!is_root(p)) rotate(left(n) ^ left(p) ? n : p);
    rotate(n);
  }
  //最後に遅延評価
  push(n);
}

inline node* find_root(node *n){
  if(n == NULL) return NULL;
  while(n -> l){
    //関与するノードの遅延評価を行う
    push(n);
    n = n -> l;
  }
  return n;
}

//返り値はnじゃないよ
inline node* expose(node *n){
  node *last = NULL;
  for(node *m = n; m; m = m -> p){
    splay(m);
    m -> r = last;
    last = m;
  }
  splay(n);
  return last;
}

void link(node *m, node *n){
  expose(m), expose(n);
  m -> p = n;
  //mの部分木分増やす
}

void cut(node *n){
  expose(n);
  //nの部分木分減らす
  n -> l -> p = NULL;
  n -> l = NULL;
}

//非連結なら-1
int LCA(node *a,node *b){
  expose(a);
  node *ret = expose(b);
  if(a->p == (node*)NULL) return -1;
  else return ret->id;
}


const int MAXN = 200005;
node *V[MAXN];
template<typename F, typename T>
struct segtree{
	int sz;
	vector<T>seg;
	const F f;
	const T e;
	segtree(int n, const F f, const T e): f(f), e(e) {
		sz = 1;
		while(sz < n) sz <<= 1;
		seg.assign(2*sz, e);
	}
	void init(int n){
		sz = 1;
		while(sz < n) sz <<= 1;
		seg.assign(2*sz, e);
	}
	//mrg...apply f or not
	void update(int a, T p, bool mrg){
		a += sz-1;
		if(mrg) seg[a] = f(seg[a], p);
		else seg[a] = p;
		while(a){
			a = (a-1)/2;
			seg[a] = f(seg[a*2+1], seg[a*2+2]);
		}
	}
	void make(vector<T>a){
		rep(i, a.size()) seg[i+sz-1] = a[i];
		for(int i=sz-2;i>=0;i--) seg[i] = f(seg[i*2+1], seg[i*2+2]);
	}
	T query(int a, int b){
		a += sz-1, b += sz-1;
		T L = e, R = e;
		while(a <= b){
			if((a&1) == 0) { L = f(L, seg[a++]); }
			if((b&1) == 1) { R = f(seg[b--], R); }
			if(a > b) break;
			a = (a-1) >> 1;
			b = (b-1) >> 1;
		}
		return f(L, R);
	}
	int find_left(int a, int b, int k, int l, int r, T v){
		if(r < a || b < l) return INF;
		if(a <= l && r <= b){
			if(f(seg[k], v) == seg[k]){
				while(k < sz-1){
					if(f(seg[k*2+1], v) == seg[k*2+1]) k = k*2+1;
					else k = k*2+2;
				}
				return k - (sz-1);
			}
			return INF;
		}
		int ret = find_left(a, b, k*2+1, l, (l+r)/2, v);
		if(ret != INF) return ret;
		return find_left(a, b, k*2+2, 1+(l+r)/2, r, v);
	}
	//NOT VERIFIED
	int find_right(int a, int b, int k, int l, int r, T v){
		if(r < a || b < l) return -INF;
		if(a <= l && r <= b){
			if(f(seg[k], v) == seg[k]){
				while(k < sz-1){
					if(f(seg[k*2+2], v) == seg[k*2+2]) k = k*2+2;
					else k = k*2+1;
				}
				return k - (sz-1);
			}
			return -INF;
		}
		int ret = find_right(a, b, k*2+2, 1+(l+r)/2, r, v);
		if(ret != -INF) return ret;
		return find_right(a, b, k*2+1, l, (l+r)/2, v);
	}
	//[a, b]でf(*, v)=*となる最小の*を返す 無ければINF
	int find_left(int a, int b, T v){
		return find_left(a, b, 0, 0, sz-1, v);
	}
	//NOT VERIFIED
	//[a, b]でf(*, v)=*となる最大の*を返す 無ければ-INF
	int find_right(int a, int b, T v){
		return find_right(a, b, 0, 0, sz-1, v);
	}
	
};
auto f = [](P a, P b){ return max(a, b); };
P e = mp(-1e18, -1e18);
segtree<decltype(f), decltype(e)>seg((1<<18), f, e);

P get(int v, int ch){
	P ret = e;
	if(ch != up[0][v] and v != 1) chmax(ret, mp(val[up[0][v]], up[0][v]));
	if(1<=ch and ch<=n and beg[v]<=ran[ch] and ran[ch]<=upp[v]){
		chmax(ret, seg.query(beg[v], ran[ch]-1));
		chmax(ret, seg.query(ran[ch]+1, upp[v]));
	}
	else chmax(ret, seg.query(beg[v], upp[v]));
	if(ret.a<0) return mp(v, v);
	return ret;
}

void solve(){
	cin>>n;
	rep(i, n-1){
		int a, b; cin >> a >> b;
		edge[a].pb(b);
		edge[b].pb(a);
	}
	kaede.prepare();
	vc<int>used(n+1, 0);
	vc<int>dist(n+1, INF);
	vc<int>arr(n+1);
	queue<int>que;
	que.push(1);
	dist[1] = 0;
	int idx = 1;
	while(!que.empty()){
		auto q = que.front(); que.pop();
		if(used[q]) continue;
		used[q] = 1;
		arr[idx] = q;
		ran[q] = idx++;
		for(auto a:edge[q]){
			chmin(dist[a], dist[q]+1);
			if(!used[a]) que.push(a);
		}
	}
	repn(i, n) val[i] = i;
	repn(i, n) V[i] = new node(i);
	repn(i, n){
		beg[i] = INF, upp[i] = -INF;
		int cnt = 0;
		for(auto a:edge[i]){
			if(dist[i]+1 == dist[a]){
				chmin(beg[i], ran[a]);
				chmax(upp[i], ran[a]);
				cnt++;
			}
		}
		if(beg[i] <= upp[i]){
		assert(upp[i]-beg[i]+1==cnt);
			P p = mp(-1, -1);
			for(int j=beg[i];j<=upp[i];j++){
				chmax(p, mp(val[arr[j]], arr[j]));
			}
			link(V[i], V[p.b]);
		}
	}
/*	repn(i, n){
	    expose(V[i]);
		cout << find_root(V[i])->id << endl;
	}*/
	for(int i=1;i<=n;i++) seg.update(ran[i], mp(val[i], i), false);
	vc<vc<int>>chain(n+1, vc<int>());
	repn(i, n) chain[i].resize(hld_sz[i]+1, 0);
	repn(i, n) chain[hld_cmp[i]][hld_num[i]] = i;
	using st = segtree<decltype(f), decltype(e)>;
	auto segh = vc<st>();
	segh.reserve(n+1);
	rep(i, n+1){
		segh.pb(st((int)(hld_sz[i]+2) * 2, f, e));
	}
	P reve = mp(1e18, 1e18);
	repn(i, n){
		if(hld_sz[i] <= 2) continue;
		for(int j=2;j<hld_sz[i];j++){
			int v = chain[i][j];
			int w = chain[i][j+1];
			auto xx = get(v, w);
			assert(xx.b != v);
			bool f = xx.b == chain[i][j-1];
			segh[i].update(j, (!f?reve:e), false);
		//	cout<<v << " " << chain[i][j-1] << " " << xx << " " << f << endl;
		}
	}
	int pre = 0;
	int q; cin >> q;
	while(q--){
		int u, v; cin >> u >> v;
		//cout<<pre<<endl;
		u = (u+pre)%n; if(!u) u = n;
		v = (v+pre)%n; if(!v) v = n;
		if(u==v)continue;
		//cout<<u<<" "<<v<<endl;
		//swap val[u] and val[v]
		swap(val[u], val[v]);
		seg.update(ran[u], mp(val[u], u), false);
		seg.update(ran[v], mp(val[v], v), false);
		//repn(i, n) o(seg.query(i, i));
		for(auto see:vc<int>({u, v})){
			int r = hld_num[see];
			int cc = hld_cmp[see];
			{
				int U = up[0][see];
				if(U >= 1){
					int nxtt=-1;
					if(cc == hld_cmp[U]) nxtt = see;
					else if(hld_num[U] != hld_sz[hld_cmp[U]]){
						nxtt = chain[hld_cmp[U]][hld_num[U]+1];
					}
					
					auto xx = get(U, nxtt);
					bool f = xx.b == up[0][U];
					int nc = hld_cmp[U];
					segh[nc].update(hld_num[U], (!f?reve:e), false);
				}
			}
			if(r+1 < hld_sz[cc]){
				auto xx = get(chain[cc][r+1], chain[cc][r+2]);
				bool f = xx.b == chain[cc][r];
				assert(chain[cc][r] == see);
				segh[cc].update(r+1, (!f?reve:e), false);
			}
		}
		for(auto pr:vc<int>({up[0][u], up[0][v]})){
			if(pr < 1) continue;
			if(beg[pr] > upp[pr]) continue;
			auto k = seg.query(beg[pr], upp[pr]);
			cut(V[pr]);
			link(V[pr], V[k.b]);
		}
		//for(int i=1;i<=n;i++) o(segh[hld_cmp[i]].query(hld_num[i], hld_num[i]));
		//return;
		//u -(up)-> w
		auto xx = get(u, -1);
        //o(xx); 
		if(xx.b != up[0][u]){
			expose(V[xx.b]);
			pre = find_root(V[xx.b])->id;
			o(pre);
		}
		else{
			int prevv = u;
			int cur = xx.b;
			while(cur != 1){
			    //cout<<cur<<" "<<prevv<<endl;
				int cc = hld_cmp[cur];
				int len = hld_sz[cc];
				int zan = hld_num[cur];
				//cout<<cc<<" "<<len<<" "<<zan<<endl;
				if(zan == 1 or zan == len or cc != hld_cmp[prevv]){
					auto yy = get(cur, prevv);
					if(yy.b != up[0][cur]){
						expose(V[yy.b]);
						pre = find_root(V[yy.b])->id;
						o(pre); goto nxt;
					}
					prevv = cur;
					cur = yy.b;
				}
				else{
					assert(2 <= zan and zan < len and cc == hld_cmp[prevv]);
					auto x = segh[cc].find_right(2, zan, reve);
					if(x < 0){
						prevv = chain[cc][2];
						cur = chain[cc][1];
					}
					else{
						prevv = chain[cc][x+1];
						cur = chain[cc][x];
						//cout<<cur<<" "<<prevv<<"D"<<endl;
						auto yy = get(cur, prevv);
						if(yy.b == up[0][cur]){
							cout<<x<<endl;
						    cout<<cur<<" "<<prevv<<" "<<segh[cc].query(x, x)<<" "<<yy<<" "<<up[0][cur]<<endl;
						    assert(false);
						}
						expose(V[yy.b]);
						pre = find_root(V[yy.b])->id;
						o(pre); goto nxt;
					}
				}
			}
			nxt:;
			if(cur != 1) continue;
			//cout<<cur<<" "<<prevv<<endl;
			auto xx = get(cur, prevv);
			if(xx.b == 1){
			    pre = 1;
			    o(1);
			    continue;
			}
			expose(V[xx.b]);
			pre = find_root(V[xx.b])->id;
			o(pre);
		}
	}
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t = 1; //cin >> t;
	while(t--) solve();
}
0