結果

問題 No.898 tri-βutree
コンテスト
ユーザー season1618
提出日時 2019-10-04 23:35:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,326 bytes
コンパイル時間 1,830 ms
コンパイル使用メモリ 194,832 KB
実行使用メモリ 57,616 KB
最終ジャッジ日時 2024-10-03 09:48:33
合計ジャッジ時間 12,894 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int INF=1e9;
vector<int> g[size];
map<int,map<int,long>> len;
int par[size];int depth[size]={};
void dfs(int p,int v){
	for(int u:g[v]){
		if(u==p) continue;
        par[u]=v;depth[u]=depth[v]+1;
		dfs(v,u);
	}return;
}
int main(){
	int N;cin>>N;
	rep(i,0,N-1){
        int a,b,w;
		cin>>a>>b>>w;
		g[a].push_back(b);
		g[b].push_back(a);
		len[a][b]=w;
		len[b][a]=w;
	}
	par[0]=-1;dfs(-1,0);
	int Q;cin>>Q;
	vector<pair<int,int>> x(3);//print(par,N);
    long sum;
	rep(i,0,Q){
        int a,b,c;
		cin>>a>>b>>c;
        x[0]={-depth[a],a};x[1]={-depth[b],b};x[2]={-depth[c],c};
        sort(x.begin(),x.end());
        map<pair<int,int>,int> count;
        int node[N]={};
		sum=0;
		rep(j,0,3){
            if(node[a]&&node[b]&&node[c]) break;
			int v=x[j].second;node[v]=1;
			while(v!=0){
                if(count[{v,par[v]}]>0) break;
                count[{v,par[v]}]++;
				sum+=len[v][par[v]];
				v=par[v];node[v]=1;
                if(v==x[0].second||v==x[1].second||v==x[2].second) break;
			}
		}
        cout<<sum<<endl;
	}
}
0