結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:38:32 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,299 bytes |
コンパイル時間 | 1,978 ms |
コンパイル使用メモリ | 165,484 KB |
実行使用メモリ | 30,720 KB |
最終ジャッジ日時 | 2024-11-08 22:21:55 |
合計ジャッジ時間 | 13,089 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 1 |
other | TLE * 1 -- * 20 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define REP(i,m,n) for(int i=(m);i<(n);i++)#define rep(i,n) REP(i,0,n)#define pb push_back#define mp make_pair#define all(c) (c).begin(),(c).end()#define rall(c) (c).rbegin(),(c).rend()#define double long doubletypedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;const ll inf=1e9+7;const ll mod=1e9+7;vector<vector<pll> >G(100010);vector<pll>par(100010);vector<ll>dis(100010);void dfs(ll i,ll p,ll d,ll def){par[i].first=p;par[i].second=def-1;dis[i]=d;rep(j,G[i].size()){if(G[i][j].first==p)continue;dfs(G[i][j].first,i,d+G[i][j].second,def+1);}}ll LCA(ll x,ll y){ll s=par[x].second+1;ll t=par[y].second+1;if(t>s){return LCA(x,par[y].first);}else if(t<s){return LCA(par[x].first,y);}else{if(x==y)return x;else return LCA(par[x].first,par[y].first);}}int main(){ll n;cin>>n;rep(i,n-1){ll u,v,w;cin>>u>>v>>w;G[u].pb(mp(v,w));G[v].pb(mp(u,w));}dfs(0LL,(ll)-1,0LL,0LL);ll q;cin>>q;while(q){ll x,y,z;cin>>x>>y>>z;cout<<dis[x]+dis[y]+dis[z]-dis[LCA(x,y)]-dis[LCA(y,z)]-dis[LCA(z,x)]<<'\n';q--;}}