結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:14:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 476 ms / 4,000 ms |
コード長 | 2,283 bytes |
コンパイル時間 | 927 ms |
コンパイル使用メモリ | 99,236 KB |
実行使用メモリ | 31,232 KB |
最終ジャッジ日時 | 2024-11-08 22:16:59 |
合計ジャッジ時間 | 10,470 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)using namespace std;typedef long long ll;const ll MOD=1e9+7;//入力const int MAX_V=100010;const int MAX_LOG_V=20;vector<int> G[MAX_V]; //グラフの隣接リスト表現int root; //根ノードの番号int parent[MAX_LOG_V][MAX_V]; //親を2^k回辿って到達する頂点(根を通り過ぎる場合は-1)int depth[MAX_V]; //根からの深さvoid dfs(int v,int p,int d){parent[0][v]=p;depth[v]=d;for(int i=0;i<G[v].size();i++){if(G[v][i]!=p) dfs(G[v][i],v,d+1);}}//初期化void init(int V){//parent[0]とdepthを初期化するdfs(root,-1,0);//parentを初期化するfor(int k=0;k+1<MAX_LOG_V;k++){for(int v=0;v<V;v++){if(parent[k][v]<0) parent[k+1][v]=-1;else parent[k+1][v]=parent[k][parent[k][v]];}}}//uとvのLCAを求めるint lca(int u,int v){//uとvの深さが同じになるまで親を辿るif(depth[u]>depth[v]) swap(u,v);for(int k=0;k<MAX_LOG_V;k++){if((depth[v]-depth[u])>>k&1){v=parent[k][v];}}if(u==v) return u;//二分探索でLCAを求めるfor(int k=MAX_LOG_V-1;k>=0;k--){if(parent[k][u]!=parent[k][v]){u=parent[k][u];v=parent[k][v];}}return parent[0][u];}ll val[100010];int N;vector<pair<int,ll>> g[100010];void setVal(int now,int par,ll v){val[now]=v;for(int i=0;i<g[now].size();i++){int nex=g[now][i].first;ll c=g[now][i].second;if(nex==par) continue;setVal(nex,now,v+c);}}int main(){cin>>N;rep(i,N-1){int a,b,c;cin>>a>>b>>c;g[a].push_back(mkp(b,c));g[b].push_back(mkp(a,c));G[a].push_back(b);G[b].push_back(a);}root=0;init(N);setVal(0,-1,0ll);int Q;cin>>Q;for(int i=0;i<Q;i++){int x,y,z;cin>>x>>y>>z;ll ans=val[x]+val[y]+val[z];int u=lca(x,y);int v=lca(x,z);int w=lca(z,y);ans-=(val[u]+val[v]+val[w]);int p=lca(u,z);//ans+=val[p];cout<<ans<<endl;}return 0;}