結果
問題 | No.898 tri-βutree |
ユーザー |
|
提出日時 | 2019-10-04 22:18:57 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 271 ms / 4,000 ms |
コード長 | 2,394 bytes |
コンパイル時間 | 1,399 ms |
コンパイル使用メモリ | 162,932 KB |
実行使用メモリ | 33,024 KB |
最終ジャッジ日時 | 2024-11-08 22:17:07 |
合計ジャッジ時間 | 7,633 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define F first#define S second#define R cin>>#define Z class#define ll long long#define ln cout<<'\n'#define in(a) insert(a)#define pb(a) push_back(a)#define pd(a) printf("%.10f\n",a)#define mem(a) memset(a,0,sizeof(a))#define all(c) (c).begin(),(c).end()#define iter(c) __typeof((c).begin())#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)#define rep(i,n) REP(i,0,n)#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)template<Z A>void pr(A a){cout<<a;ln;}template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};typedef pair<ll,ll> P;ll dep[100010],dep2[100010];ll par[100010][19];vector<P> v[100010];void dfs(ll x,ll y,ll d){dep[x]=d;for(int i=0; i<v[x].size(); i++){ll z=v[x][i].F;if(z==y) continue;par[z][0]=x;dfs(z,x,d+1);}}void dfs2(ll x,ll y,ll d){dep2[x]=d;for(int i=0; i<v[x].size(); i++){ll z=v[x][i].F;if(z==y) continue;dfs2(z,x,d+v[x][i].S);}}int lca(int a,int b){if(dep[a]<dep[b]) swap(a,b);for(int i=0; i<19; i++){if((dep[a]-dep[b])&(1<<i)) a=par[a][i];}if(a==b) return a;for(int i=18;i>=0;i--){if(par[a][i]!=par[b][i]) a=par[a][i],b=par[b][i];}return par[a][0];}int n;void init() {memset(par,0,sizeof(par));dfs(0,-1,0);for(int i=0; i<18; i++)for(int j=0; j<n; j++) par[j][i+1]=par[par[j][i]][i];dfs2(0,-1,0);}ll D(int x,int y) {return dep2[x]+dep2[y]-dep2[lca(x,y)]*2;}void Main() {cin >> n;rep(i,n-1) {ll x,y,z;cin >> x >> y >> z;v[x].pb(P(y,z));v[y].pb(P(x,z));}init();ll T;cin >> T;while(T--) {ll x,y,z;cin >> x >> y >> z;ll r=lca(x,y);r=lca(r,z);if(r==y) swap(x,y);else if(r==z) swap(x,z);else if(lca(x,y)!=r) swap(x,z);else if(lca(x,z)!=r) swap(x,y);ll d1=D(x,y),d2=D(x,z),d3=D(y,z);ll c1=D(x,r),c2=D(y,r),c3=D(z,r);pr(c1+c2+c3-D(r,lca(y,z)));}}int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}