結果

問題 No.898 tri-βutree
ユーザー 沙耶花沙耶花
提出日時 2019-10-04 22:03:03
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 704 ms / 4,000 ms
コード長 3,916 bytes
コンパイル時間 1,996 ms
コンパイル使用メモリ 187,432 KB
実行使用メモリ 50,084 KB
最終ジャッジ日時 2023-08-08 15:58:50
合計ジャッジ時間 15,252 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 363 ms
50,084 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 679 ms
38,056 KB
testcase_08 AC 672 ms
38,180 KB
testcase_09 AC 682 ms
38,192 KB
testcase_10 AC 704 ms
37,988 KB
testcase_11 AC 701 ms
38,196 KB
testcase_12 AC 695 ms
38,276 KB
testcase_13 AC 690 ms
38,120 KB
testcase_14 AC 682 ms
38,004 KB
testcase_15 AC 669 ms
38,040 KB
testcase_16 AC 681 ms
37,980 KB
testcase_17 AC 685 ms
38,064 KB
testcase_18 AC 692 ms
38,048 KB
testcase_19 AC 693 ms
37,984 KB
testcase_20 AC 677 ms
38,040 KB
testcase_21 AC 680 ms
37,984 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000

vector<int> ind;
vector<long long> D;

template <typename T>
struct segtree{
	//元データx[i]はv[n+i]
	//v[i]の親はv[i/2],子はv[i*2]とv[i*2+1]
	vector<T> v;
	int n;
	
	const T init_value = 0;
	
	segtree(vector<T> &x){
		n=1;
		while(true){
			if(n>=x.size())break;
			n*=2;
		}
		v.resize(2*n,init_value);
		
		for(int i=0;i<x.size();i++){
			v[n+i]=x[i];
		}
		for(int i=n-1;i>=0;i--){
			v[i]=func(v[i*2],v[i*2+1]);
		}
	}

	void update(int x,T val){
		x+=n;
		v[x]=val;
		while(true){
			x=(x)/2;
			v[x]=func(v[x*2],v[x*2+1]);
			if(x<=0)break;
		}
	}
	
	//区間[l,r)におけるクエリ処理
	T query(int l,int r){
		T res = init_value;
		if(l>=r)return res;
		l+=n;r+=n;
		while(true){
			if(l%2==1){
				res=func(v[l],res);
				l++;
			}
			if(r%2==1){
				res=func(v[r-1],res);
				r--;
			}
			if(l>=r)break;
			l/=2;r/=2;
		}
		return res;
	}
	T func(T a,T b){
		return a+b;
	}
	
	void show(){
		int n = 1;
		for(int i=1;i<v.size();i++){
			for(int j=0;j<n;j++){
				if(j!=0)cout<<' ';
				cout<<v[i+j];
			}
			cout<<endl;
			i+=n-1;
			n*=2;
		}
	}
	
};

struct lca{
	
	vector<int> depth;//depth[i] 頂点iの深さ
	vector<vector<int>> parents;//parents[i][j] 頂点iから2^j個上の親
	
	int max_j = 30;
	
	lca(int n,vector<vector<int>> &E){
		depth.assign(E.size(),-1);
		parents.assign(E.size(),vector<int>(max_j,-1));
		
		stack<int> s;
		s.push(n);
		depth[n] = 0;
		while(s.size()!=0){
			int k = s.top();
			s.pop();
			for(int i=0;i<E[k].size();i++){
				int x = E[k][i];
				if(depth[x]!=-1)continue;
				s.push(x);
				depth[x] = depth[k]+1;
				for(int j=0;j<max_j;j++){
					if(j==0){
						parents[x][j] = k;
					}
					else{
						parents[x][j] = parents[parents[x][j-1]][j-1];
					}
					if(parents[x][j] == -1)break;
				}
			}
		}
	}
	
	//頂点uのk番目の親
	int kth_parent(int u,int k){
		for(int i=0;i<max_j;i++){
			if(k==0)break;
			if(u==-1)break;
			if(k%2){
				u = parents[u][i];
			}
			k/=2;
		}
		return u;
	}
	
	int query(int u,int v){
		if(depth[u]<depth[v])swap(u,v);
		u = kth_parent(u,depth[u]-depth[v]);
		
		if(u==v){
			return u;
		}
		
		for(int i=max_j-1;i>=0;i--){
			if(parents[u][i]!=parents[v][i]){
				u = parents[u][i];
				v = parents[v][i];
			}
		}
		
		return parents[u][0];
		
	}
	
	int get_distance(int u,int v){
		return depth[u]+depth[v]-2*depth[query(u,v)];
	}
	
	
};

void dfs(vector<vector<pair<int,long long>>> &E,int now,int parent){
	for(int i=0;i<E[now].size();i++){
		int to = E[now][i].first;
		long long d = E[now][i].second;
		if(to==parent)continue;
		ind.push_back(to);
		D.push_back(d);
		dfs(E,to,now);
		ind.push_back(to);
		D.push_back(-d);
	}
}

long long get_dis(segtree<long long> &seg,lca &L,vector<int> &I,int x,int y){
	int p = L.query(x,y);
	int xx = I[x];
	int yy = I[y];
	int pp = I[p];
	return seg.query(0,xx+1)+seg.query(0,yy+1)-2*seg.query(0,pp+1);
}

int main(){
	
	int N;
	cin>>N;
	
	vector<vector<int>> E(N,vector<int>());
	vector<vector<pair<int,long long>>> Ew(N,vector<pair<int,long long>>());
	
	for(int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		long long w;
		cin>>w;
		
		E[a].push_back(b);
		E[b].push_back(a);
		
		Ew[a].emplace_back(b,w);
		Ew[b].emplace_back(a,w);
	}
	
	lca L(0,E);
	
	ind.push_back(0);
	D.push_back(0);
	dfs(Ew,0,-1);
	
	vector<int> I(N,-1);
	for(int i=0;i<ind.size();i++){
		if(I[ind[i]]!=-1)continue;
		I[ind[i]]=i;
	}
	
	segtree<long long> seg(D);
	
	int Q;
	cin>>Q;
	
	
	
	for(int i=0;i<Q;i++){
		int x,y,z;
		cin>>x>>y>>z;
		
		long long A = get_dis(seg,L,I,x,y);
		long long B = get_dis(seg,L,I,y,z);
		long long C = get_dis(seg,L,I,z,x);
		
		//cout<<A<<','<<B<<','<<C<<endl;
		
		cout<<(A+B+C)/2<<endl;
	}

	/*
	seg.show();
	for(int i=0;i<ind.size();i++){
		cout<<ind[i]<<',';
	}
	*/
	
	
	return 0;
}
0