結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:03:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 698 ms / 4,000 ms |
コード長 | 3,916 bytes |
コンパイル時間 | 2,334 ms |
コンパイル使用メモリ | 189,336 KB |
実行使用メモリ | 50,388 KB |
最終ジャッジ日時 | 2024-11-08 22:11:57 |
合計ジャッジ時間 | 13,911 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 1000000000000000vector<int> ind;vector<long long> D;template <typename T>struct segtree{//元データx[i]はv[n+i]//v[i]の親はv[i/2],子はv[i*2]とv[i*2+1]vector<T> v;int n;const T init_value = 0;segtree(vector<T> &x){n=1;while(true){if(n>=x.size())break;n*=2;}v.resize(2*n,init_value);for(int i=0;i<x.size();i++){v[n+i]=x[i];}for(int i=n-1;i>=0;i--){v[i]=func(v[i*2],v[i*2+1]);}}void update(int x,T val){x+=n;v[x]=val;while(true){x=(x)/2;v[x]=func(v[x*2],v[x*2+1]);if(x<=0)break;}}//区間[l,r)におけるクエリ処理T query(int l,int r){T res = init_value;if(l>=r)return res;l+=n;r+=n;while(true){if(l%2==1){res=func(v[l],res);l++;}if(r%2==1){res=func(v[r-1],res);r--;}if(l>=r)break;l/=2;r/=2;}return res;}T func(T a,T b){return a+b;}void show(){int n = 1;for(int i=1;i<v.size();i++){for(int j=0;j<n;j++){if(j!=0)cout<<' ';cout<<v[i+j];}cout<<endl;i+=n-1;n*=2;}}};struct lca{vector<int> depth;//depth[i] 頂点iの深さvector<vector<int>> parents;//parents[i][j] 頂点iから2^j個上の親int max_j = 30;lca(int n,vector<vector<int>> &E){depth.assign(E.size(),-1);parents.assign(E.size(),vector<int>(max_j,-1));stack<int> s;s.push(n);depth[n] = 0;while(s.size()!=0){int k = s.top();s.pop();for(int i=0;i<E[k].size();i++){int x = E[k][i];if(depth[x]!=-1)continue;s.push(x);depth[x] = depth[k]+1;for(int j=0;j<max_j;j++){if(j==0){parents[x][j] = k;}else{parents[x][j] = parents[parents[x][j-1]][j-1];}if(parents[x][j] == -1)break;}}}}//頂点uのk番目の親int kth_parent(int u,int k){for(int i=0;i<max_j;i++){if(k==0)break;if(u==-1)break;if(k%2){u = parents[u][i];}k/=2;}return u;}int query(int u,int v){if(depth[u]<depth[v])swap(u,v);u = kth_parent(u,depth[u]-depth[v]);if(u==v){return u;}for(int i=max_j-1;i>=0;i--){if(parents[u][i]!=parents[v][i]){u = parents[u][i];v = parents[v][i];}}return parents[u][0];}int get_distance(int u,int v){return depth[u]+depth[v]-2*depth[query(u,v)];}};void dfs(vector<vector<pair<int,long long>>> &E,int now,int parent){for(int i=0;i<E[now].size();i++){int to = E[now][i].first;long long d = E[now][i].second;if(to==parent)continue;ind.push_back(to);D.push_back(d);dfs(E,to,now);ind.push_back(to);D.push_back(-d);}}long long get_dis(segtree<long long> &seg,lca &L,vector<int> &I,int x,int y){int p = L.query(x,y);int xx = I[x];int yy = I[y];int pp = I[p];return seg.query(0,xx+1)+seg.query(0,yy+1)-2*seg.query(0,pp+1);}int main(){int N;cin>>N;vector<vector<int>> E(N,vector<int>());vector<vector<pair<int,long long>>> Ew(N,vector<pair<int,long long>>());for(int i=0;i<N-1;i++){int a,b;cin>>a>>b;long long w;cin>>w;E[a].push_back(b);E[b].push_back(a);Ew[a].emplace_back(b,w);Ew[b].emplace_back(a,w);}lca L(0,E);ind.push_back(0);D.push_back(0);dfs(Ew,0,-1);vector<int> I(N,-1);for(int i=0;i<ind.size();i++){if(I[ind[i]]!=-1)continue;I[ind[i]]=i;}segtree<long long> seg(D);int Q;cin>>Q;for(int i=0;i<Q;i++){int x,y,z;cin>>x>>y>>z;long long A = get_dis(seg,L,I,x,y);long long B = get_dis(seg,L,I,y,z);long long C = get_dis(seg,L,I,z,x);//cout<<A<<','<<B<<','<<C<<endl;cout<<(A+B+C)/2<<endl;}/*seg.show();for(int i=0;i<ind.size();i++){cout<<ind[i]<<',';}*/return 0;}