結果
問題 | No.901 K-ary εxtrεεmε |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:33:36 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 198 ms / 3,000 ms |
コード長 | 4,487 bytes |
コンパイル時間 | 1,189 ms |
コンパイル使用メモリ | 98,148 KB |
実行使用メモリ | 46,724 KB |
最終ジャッジ日時 | 2024-10-04 06:24:04 |
合計ジャッジ時間 | 7,178 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 29 |
ソースコード
#include <iostream>#include <vector>#include <map>#include <algorithm>#define llint long long#define inf 1e18using namespace std;struct edge{llint to, cost;edge(){}edge(llint a, llint b){to = a, cost = b;}};typedef pair<int, int> P;struct HLD{int V, logV;vector<P> mp;map<P, int> mp2;vector<P> parent;//subtree of v is [pre_order[v], back_order[v]]vector<int> pre_order;vector<int> back_order;int order;int global_id, local_id;vector<int> size, depth;vector<vector<int> > prev;HLD(){}void predfs(vector<int> G[], int v, int p, int d){size[v] = 1, depth[v] = d, prev[v][0] = p;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;predfs(G, G[v][i], v, d+1);size[v] += size[G[v][i]];}}void maindfs(vector<int> G[], int v, int p){mp[v] = make_pair(global_id, local_id);mp2[make_pair(global_id, local_id)] = v;pre_order[v] = ++order;if(G[v].size() == 1 && G[v][0] == p){back_order[v] = order;return;}vector<P> vec;for(int i = 0; i < G[v].size(); i++){if(G[v][i] == p) continue;vec.push_back(make_pair(size[G[v][i]], G[v][i]));}sort(vec.rbegin(), vec.rend());local_id++;if(vec.size() >= 1) maindfs(G, vec[0].second, v);for(int i = 1; i < vec.size(); i++){parent.push_back(mp[v]);global_id++, local_id = 0;maindfs(G, vec[i].second, v);}back_order[v] = order;}int getLCA(int u, int v){int x = u, y = v;if(depth[y] > depth[x]) swap(x, y);for(int i = logV-1; i >= 0; i--){if(depth[x] - (1<<i) >= depth[y]) x = prev[x][i];}if(x == y) return x;for(int i = logV-1; i >= 0; i--){if(prev[x][i] != prev[y][i]){x = prev[x][i];y = prev[y][i];}}x = prev[x][0];return x;}void pathcalc(int v, int lca, vector<pair<int, P> > &dest){int gid = mp[v].first, lid = mp[v].second;int Gid = mp[lca].first, Lid = mp[lca].second;while(Gid != gid){dest.push_back(make_pair(gid, make_pair(0, lid)));int ngid = parent[gid].first, nlid = parent[gid].second;gid = ngid, lid = nlid;}dest.push_back(make_pair(gid, make_pair(Lid, lid)));}void init(vector<int> G[], int V) // The tree must be 1-indexed.{this->V = V, logV = 0;for(int t = V; t; t/=2) logV++;prev.resize(V+1);for(int i = 0; i <= V; i++) prev[i].resize(logV);size.resize(V+1), depth.resize(V+1);predfs(G, 1, 0, 0);prev[0][0] = 0;for(int i = 1; i < logV; i++){for(int j = 1; j <= V; j++){prev[j][i] = prev[prev[j][i-1]][i-1];}}mp.resize(V+1), mp2.clear();parent.clear(), parent.push_back(make_pair(-1, -1));pre_order.resize(V+1), back_order.resize(V+1);global_id = local_id = 0, order = 0;maindfs(G, 1, 0);}void path(int u, int v, vector<pair<int, P> > &dest){dest.clear();int lca = getLCA(u, v);pathcalc(u, lca, dest);pathcalc(v, lca, dest);pair<int, P> p = make_pair(mp[lca].first, make_pair(mp[lca].second, mp[lca].second));for(int i = 0; i < dest.size(); i++){if(dest[i] == p){dest.erase(dest.begin()+i);return ;}}}void toOrder(vector<pair<int, P> > &src, vector<P> &dest){dest.clear();for(int i = 0; i < src.size(); i++){int u = mp2[make_pair(src[i].first, src[i].second.first)], v = mp2[make_pair(src[i].first, src[i].second.second)];dest.push_back(make_pair(pre_order[u], pre_order[v]));}}};llint n, Q;vector<int> G[100005];vector<edge> g[100005];llint dist[100005];HLD hld;void dfs(int v, int p, llint d){dist[v] = d;for(int i = 0; i < g[v].size(); i++){if(g[v][i].to == p) continue;dfs(g[v][i].to, v, d + g[v][i].cost);}}llint calc(llint s, llint t){llint lca = hld.getLCA(s, t);return dist[s] + dist[t] - 2 * dist[lca];}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n;llint u, v, w;for(int i = 1; i <= n-1; i++){cin >> u >> v >> w;u++, v++;G[u].push_back(v);G[v].push_back(u);g[u].push_back(edge(v, w));g[v].push_back(edge(u, w));}hld.init(G, n);dfs(1, -1, 0);cin >> Q;for(int q = 0; q < Q; q++){llint k, x;vector<P> vec;cin >> k;for(int i = 0; i < k; i++){cin >> x;x++;vec.push_back(make_pair(hld.pre_order[x], x));}sort(vec.begin(), vec.end());llint ans = 0;for(int i = 0; i < k; i++){ans += calc(vec[i].second, vec[(i+1)%k].second);}cout << ans/2 << "\n";}flush(cout);return 0;}