結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000
vector<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] i2^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;
}
}
}
}
//uk
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0