Submission #534805

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
struct SegmentTree{
	int n_;
	vector<int> seg;
	// [1,N]
	SegmentTree(int N){
		n_ = 1;
		while(n_ < N ) n_ *= 2;
		seg.resize(2*n_,2e9); //要設定
	}
	void add(int i,int v){
		i += n_-1;
		seg[i] = v;
		i /= 2;
		while(i){
			seg[i] = min(seg[i*2],seg[i*2+1]); //要設定
			i /= 2;
		}
	}
	void add(int i,int j,int v){
		assert(i == j);
		add(i,v);
	}
	int get(int l,int r,int k,int a,int b){
		if( b < l || r < a ) return 2e9; //要設定
		if( l <= a && b <= r ){
			return seg[k];
		}
		int m = (a+b)/2;
		return min(get(l,r,k*2,a,m),get(l,r,k*2+1,m+1,b)); //要設定
	}
	// x未満の値の最小位置を返す
	int getMinPos(int l,int r,int x,int k,int a,int b){
		if( b < l || r < a ) return -1; //要設定
		if( b == a ){
			return seg[k] < x ? seg[k] : -1;
		}

		int m = (a+b)/2;
		if( get(l,r,k*2,a,m) < x ) return getMinPos(l,r,x,k*2,a,m);
		if( get(l,r,k*2+1,m+1,b) < x ) return getMinPos(l,r,x,k*2+1,m+1,b);
		return -1;
	}
	int getMaxPos(int l,int r,int x,int k,int a,int b){
		if( b < l || r < a ){
			//cout << "[" << a << "," << b << "] [" << l << "," << r << "]" << endl;
			return -1; //要設定
		}
		if( b == a ){
			return seg[k] < x ? seg[k] : -1;
		}
		int m = (a+b)/2;
		
		if( get(l,r,k*2+1,m+1,b) < x ){
		//	cout << "kotti" << endl;
			return getMaxPos(l,r,x,k*2+1,m+1,b);
		}
		if( get(l,r,k*2,a,m) < x ){
			return getMaxPos(l,r,x,k*2,a,m);
		}
		return -1;
	}
	inline int get(int l,int r){
		return get(l,r,1,1,n_);
	}
	inline int getMinPos(int l,int r,int x){
		return getMinPos(l,r,x,1,1,n_);
	}
	inline int getMaxPos(int l,int r,int x){
		return getMaxPos(l,r,x,1,1,n_);
	}
};



struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};


class Tree{
public:
	//[0,n)
	int n,logn,root;
	vector<vector<int>> child;
	vector<vector<int>> parent;
	vector<pair<int,int>> edges;
	vector<int> depth;
	Tree(int n_,vector<pair<int,int>> es,int root) : root(root){
		edges = es;
		n = n_;
		logn = 0;
		while(n_){
			++logn;
			n_ /= 2;
		}
		parent.resize(logn,vector<int>(n,-1));
		depth.resize(n,-1);
		child.resize(n);
		vector<vector<int>> g(n);
		for( auto e : es ){
			g[e.first].push_back(e.second);
			g[e.second].push_back(e.first);
		}
		dfs(g);
		gen_lca();
		verify();
	}
	bool verify(){
		for(int i = 0 ; i < n ; i++)
			assert( depth[i] != -1 );
	}
	int lca(int x,int y){
		if( depth[x] < depth[y] )swap(x,y);
		int d = depth[x] - depth[y];
		for(int i = 0 ; i < logn ; i++)
			if( d >> i & 1 ) x = parent[i][x];
		if( x == y ) return x;
		
		for(int i = logn-1 ; i >= 0 ; i--){
			if( parent[i][x] != parent[i][y] ){
				x = parent[i][x];
				y = parent[i][y];
			}
		}
		return parent[0][x];
	}
	int distance(int x,int y){
		return depth[x] + depth[y] - 2 * depth[lca(x,y)];
	}
private:
	int gen_lca(){
		for(int i = 1 ; i < logn ; i++){
			for(int j = 0 ; j < n ; j++)
				if( parent[i-1][j] != -1 ) 
					parent[i][j] = parent[i-1][parent[i-1][j]];
		}
	}
	int dfs(const vector<vector<int>> &g){
		stack< array<int,3> > S;
		S.push(array<int,3>{root,-1,0});
		while( S.size() ){
			int x = S.top()[0];
			int p = S.top()[1];
			int d = S.top()[2];
			S.pop();
			parent[0][x] = p;
			depth[x] = d;
			for( auto e : g[x] ){
				if( e != p ){
					S.push(array<int,3>{e,x,d+1});
					child[x].push_back(e);
				}
			}
		}
	}
};

template<class SegmentTree> class HeavyLightDecomp{
public:
	Tree tr;
	vector< pair<int,int> > where; // (id,pos)
	vector< vector<int> > pathSeq;
	vector<SegmentTree> seg;
	HeavyLightDecomp(const Tree &tr) : tr(tr){
		// init
		where.resize(tr.n,{-1,-1});
		vector<int> subtree(tr.n);
		vector<pair<int,int>> sortedIdx;
		for(int i = 0 ; i < tr.n ; i++)
			sortedIdx.push_back({tr.depth[i],i});
		sort(sortedIdx.begin(),sortedIdx.end());
		
		// calc sizes of each subtree
		for(int I = tr.n-1 ; I >= 0 ; I--){
			int i = sortedIdx[I].second;
			subtree[i] = 1;
			for( auto e : tr.child[i] ) subtree[i] += subtree[e];
		}
		// do heavyLightDecomp Part1
		for(int I = 0 ; I < tr.n ; I++){
			int i = sortedIdx[I].second;
			if( where[i].first == -1 ){
				where[i].first = pathSeq.size();
				pathSeq.push_back(vector<int>());
			}
			where[i].second = pathSeq[where[i].first].size();
			pathSeq[where[i].first].push_back(i);
			for( auto e : tr.child[i] ){
				if( 2*subtree[e] > subtree[i] ){
					where[e].first = where[i].first;
				}
			}
		}
		// Set segtrees to each heavy-path.
		for(int i = 0 ; i < pathSeq.size() ; i++){
			int n_ = 1;
			while( n_ < pathSeq[i].size() ) n_ *= 2;
			seg.push_back(SegmentTree(n_));
		}
	}
	//加算点の重複に気をつけて
	void addToVertex(int a,int b,int v){
		int p = tr.lca(a,b);
		add(a,p,v,0); //要設定
		add(b,p,v,0); //要設定
	}
	/*
	int getToVertex(int a,int b){
		int p = tr.lca(a,b);
		return min(get(a,p,0),get(b,p,0)); //要設定
	}
	*/

	inline int upMove(int c,int p,int x){
		int id1 = where[c].first;
		int id2 = where[p].first;
		int l = where[p].second + 1;
		int r = where[c].second + 1;
		int ans = 1145141919;
		if( id1 == id2 ){
			//cout << l << " " << r << " " << x << endl;
			ans = seg[id1].getMaxPos(l,r,x); //要設定
		}else{
			ans = seg[id1].getMaxPos(1,r,x); //要設定
			if( ans == -1 ) ans = upMove(tr.parent[0][pathSeq[id1][0]],p,x);
		}
		return ans;
	}
	inline int downMove(int c,int p,int x){
		int id1 = where[c].first;
		int id2 = where[p].first;
		int l = where[p].second + 1;
		int r = where[c].second + 1;
		int ans = 1145141919;
		if( id1 == id2 ){
			ans = seg[id1].getMinPos(l,r,x); //要設定
		}else{
			int ans2 = downMove(tr.parent[0][pathSeq[id1][0]],p,x);
			if( ans2 != -1 ) ans = ans2;
			else ans = seg[id1].getMinPos(1,r,x); //要設定	
		}
		return ans;
	}
	private: 
	inline void add(int c,int p,int v,int isEdgeQuery){
		int id1 = where[c].first;
		int id2 = where[p].first;
		int l = where[p].second + 1;
		int r = where[c].second + 1;
		if( id1 == id2 ){
			seg[id1].add(l+isEdgeQuery,r,v); //要設定
		}else{
			seg[id1].add(1,r,v); //要設定
			add(tr.parent[0][pathSeq[id1][0]],p,v,isEdgeQuery);
		}
	}
	/*
	inline int get(int c,int p,int isEdgeQuery){
		int id1 = where[c].first;
		int id2 = where[p].first;
		int l = where[p].second + 1;
		int r = where[c].second + 1;
		int ans = 0;
		if( id1 == id2 ){
			ans += seg[id1].get(l+isEdgeQuery,r); //要設定
		}else{
			ans += seg[id1].get(1,r); //要設定
			ans += get(tr.parent[0][pathSeq[id1][0]],p,isEdgeQuery);
		}
		return ans;
	}
	*/

};


int value[100010];

int main(){
	int n,q;
	cin >> n >> q;
	for(int i = 0 ; i < n ; i++) cin >> value[i];

	vector< pair<int,int> > es;
	for(int i = 0 ; i < n-1 ; i++){
		int a,b;
		cin >> a >> b;
		--a,--b;
		es.push_back({a,b});
	}
	Tree tr(n,es,0);
	HeavyLightDecomp<SegmentTree> hl(tr);
	for(int i = 0 ; i < n ; i++)
		hl.addToVertex(i,i,value[i]);
	//for(int i = 0 ; i < n ; i++)
	//	cout << hl.getToVertex(i,i) << endl;
	for(int i = 0 ; i < q ; i++){
		int x,a,b;
		cin >> x >> a >> b;
		--a,--b;
		int p = tr.lca(a,b);
		//cout << x << endl;
		while(1){
			int mVal = hl.upMove(a,p,x+1);
			//cout << x << " " << mVal << endl;
			if( mVal == -1 ){
				break;					
			}else x %= mVal;
		}
		//cout << x << endl;

		while(1){
			//out << a << " "<< b << " vs " << p << endl;
			int mVal = hl.downMove(b,p,x+1);
			//cout << x << " " << mVal << endl;
			if( mVal == -1 ){
				break;					
			}else x %= mVal;
		}


		cout << x << endl;
	}
}
 

Submission Info

Judge Result