結果

問題 No.898 tri-βutree
ユーザー auauaauaua
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 double
typedef 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--;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0