結果

問題 No.901 K-ary εxtrεεmε
コンテスト
ユーザー vjudge1
提出日時 2026-09-19 11:04:22
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 229 ms / 3,000 ms
+ 496µs
コード長 2,012 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,184 ms
コンパイル使用メモリ 195,064 KB
実行使用メモリ 22,912 KB
最終ジャッジ日時 2026-09-19 11:04:37
合計ジャッジ時間 8,986 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define fore(p,c) for(auto&p:(c))
#define all(c) (c).begin(),(c).end()

int N;
vector<pair<int,int>> E[101010];
int Q;

namespace hld{
    vector<int> g[101010];
    int vid[101010],par[101010],dep[101010],sz[101010],heavy[101010],head[101010];
    int n,tim;
    void init(int N){
        n=N; tim=0;
        rep(i,0,n){ g[i].clear(); heavy[i]=-1; }
    }
    void add(int a,int b){ g[a].push_back(b); g[b].push_back(a); }
    void dfs(int cu){
        sz[cu]=1; int mx=0;
        fore(to,g[cu]){
            if(to==par[cu]) continue;
            par[to]=cu; dep[to]=dep[cu]+1;
            dfs(to); sz[cu]+=sz[to];
            if(sz[to]>mx){ mx=sz[to]; heavy[cu]=to; }
        }
    }
    void dfs2(int cu,int h){
        head[cu]=h; vid[cu]=tim++;
        if(heavy[cu]!=-1) dfs2(heavy[cu],h);
        fore(to,g[cu]) if(to!=par[cu] && to!=heavy[cu]) dfs2(to,to);
    }
    void build(){ par[0]=-1; dep[0]=0; dfs(0); dfs2(0,0); }
    int lca(int u,int v){
        for(;head[u]!=head[v];v=par[head[v]]) if(dep[head[u]]>dep[head[v]]) swap(u,v);
        return dep[u]<dep[v]?u:v;
    }
}

ll sm[101010];
void dfs(int cu,int pa=-1){
    fore(p,E[cu]){
        int to,c; tie(to,c)=p;
        if(pa==to) continue;
        sm[to]=sm[cu]+c;
        dfs(to,cu);
    }
}
ll get(int a,int b){
    return sm[a]+sm[b]-2LL*sm[hld::lca(a,b)];
}

void _main(){
    cin>>N;
    hld::init(N);
    rep(i,0,N-1){
        int a,b,c; cin>>a>>b>>c;
        E[a].push_back({b,c});
        E[b].push_back({a,c});
        hld::add(a,b);
    }
    hld::build();
    dfs(0);
    cin>>Q;
    rep(q,0,Q){
        int k; cin>>k;
        vector<pair<int,int>> v;
        rep(i,0,k){ int x; cin>>x; v.push_back({hld::vid[x],x}); }
        sort(all(v));
        ll ans=0; int n=v.size();
        rep(i,0,n) ans+=get(v[i].second,v[(i+1)%n].second);
        ans/=2;
        printf("%lld\n",ans);
    }
}

int main(){ _main(); }
0