제출 #1359251

#제출 시각아이디문제언어결과실행 시간메모리
1359251Huseyn123Roadside Advertisements (NOI17_roadsideadverts)C++20
100 / 100
41 ms14012 KiB
#include <bits/stdc++.h>
#define MAX 200001
#define INF INT_MAX
//#define int long long
using namespace std;
inline void USACO(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
int n;
vector<vector<pair<int,int>>> g;
int in[MAX],out[MAX],dep[MAX];
int par[MAX][18],sum[MAX][18];
int cnt=0;
void dfs(int v,int prev){
    in[v]=++cnt;
    for(auto x:g[v]){
        if(x.first==prev){
            continue;
        }
        par[x.first][0]=v;
        sum[x.first][0]=x.second;
        dep[x.first]=dep[v]+1;
        dfs(x.first,v);
    }
    out[v]=cnt;
}
bool f(int x,vector<int> &y){
    for(auto z:y){
        if(in[z]>=in[x] && out[z]<=out[x]){
            return true;
        }
    }
    return false;
}
int up(int v,int k){
    int s=0;
    for(int i=0;i<18;i++){
        if((k&(1<<i))){
            s+=sum[v][i];
            v=par[v][i];
        }
    }
    return s;
}
int lca(int x,vector<int> &y){
    if(f(x,y)){
        return x;
    }
    for(int i=17;i>=0;i--){
        if(f(par[x][i],y)){
            continue;
        }
        x=par[x][i];
    }
    return par[x][0];
}
void solve(){
    cin >> n;
    g.clear();
    g.resize(n);
    for(int i=0;i<n-1;i++){
        int x,y,z;
        cin >> x >> y >> z;
        g[x].push_back({y,z});
        g[y].push_back({x,z});
    }
    par[0][0]=0;
    sum[0][0]=0;
    dep[0]=0;
    dfs(0,-1);
    for(int i=1;i<18;i++){
        for(int j=0;j<n;j++){
            par[j][i]=par[par[j][i-1]][i-1];
            sum[j][i]=sum[j][i-1]+sum[par[j][i-1]][i-1];
        }
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int a[5];
        for(int j=0;j<5;j++){
            cin >> a[j];
        }
        vector<int> y;
        y.push_back(a[0]);
        int l=a[0];
        int res=0;
        for(int j=1;j<5;j++){
            vector<int> cur={a[j]};
            int new_l=lca(l,cur);
            res+=up(l,dep[l]-dep[new_l]);
            l=new_l;
            res+=up(a[j],dep[a[j]]-dep[lca(a[j],y)]);
            y.push_back(a[j]);
        }
        cout << res << "\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…