結果

問題 No.1787 Do Use Dynamic Tree
コンテスト
ユーザー Nachia
提出日時 2021-12-16 22:44:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,967 ms / 10,000 ms
コード長 8,436 bytes
コンパイル時間 2,223 ms
コンパイル使用メモリ 131,152 KB
最終ジャッジ日時 2025-01-26 23:48:49
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 isppmax_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 = isppmax_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) isppmax_rq.set(hld.idxs()[evil_heavy_child], is_parent_parent_max(evil_heavy_child));
	}

	if(heavy_child != -1) isppmax_rq.set(hld.idxs()[heavy_child], is_parent_parent_max(heavy_child));
	if(heavy_child2 != -1) isppmax_rq.set(hld.idxs()[heavy_child2], is_parent_parent_max(heavy_child2));
	isppmax_rq.set(hld.idxs()[p], is_parent_parent_max(p));
}


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;
	
	isppmax_rq = all_is_good_query::rq(N);
	rep(i,N) isppmax_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();

	{
		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];
	}

	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;
	}
	
	return 0;
} 

struct ios_do_not_sync{
	ios_do_not_sync(){
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
	}
} ios_do_not_sync_instance;
0