結果

問題 No.901 K-ary εxtrεεmε
ユーザー leaf_1415leaf_1415
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define llint long long
#define inf 1e18
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0