#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define num long long
#define t_road pair<int, num>
#define rnext first
#define rcost second
#define t_roads set<t_road>
#define graph vector<t_roads>
#define idata vector<int>
#define ndata vector<num>
#define ngrid vector<ndata>
#define inf 1e18
int nbNodes, nbQuery;
graph roads;
idata centroid_tree;
idata subtree_size;
ngrid centroid_tree_distances;
int subtree_dfs (int node, int parent) {
subtree_size[node] = 1;
for (t_road road : roads[node]) if (road.rnext != parent)
subtree_size[node] += subtree_dfs(road.rnext, node);
return subtree_size[node];
}
int centroid (int node, int parent, int compSize) {
for (t_road road : roads[node])
if (road.rnext != parent
&& subtree_size[road.rnext] > compSize)
return centroid(road.rnext, node, compSize);
return node;
}
void update_distances (int node, int parent, num distance) {
centroid_tree_distances[node].push_back(distance);
for (t_road road : roads[node]) if (road.rnext != parent)
update_distances(road.rnext, node, distance + road.rcost);
}
void decompose (int node, int parent) {
int c_size = subtree_dfs(node, -1);
int centri = centroid(node, -1, c_size >> 1);
update_distances(centri, -1, 0);
centroid_tree[centri] = parent;
while (roads[centri].size() != 0) {
t_road road = *(roads[centri].begin());
roads[centri].erase(road);
roads[road.rnext].erase({ centri, road.rcost });
decompose(road.rnext, centri);
}
}
ndata query_metadata;
void enable (int start) {
int id = 0;
int node = start;
while (node != -1) {
query_metadata[node] = min(
query_metadata[node],
centroid_tree_distances[start][id]
);
node = centroid_tree[node];
id ++;
}
}
void reset (int node) {
while (node != -1) {
query_metadata[node] = inf;
node = centroid_tree[node];
}
}
num query (int start) {
num res = inf;
int id = 0;
int node = start;
while (node != -1) {
res = min(
res,
query_metadata[node] + centroid_tree_distances[start][id]
);
node = centroid_tree[node];
id ++;
}
return res;
}
void Init(int N, int A[], int B[], int D[]) {
nbNodes = N;
roads.resize(nbNodes);
centroid_tree.resize(nbNodes);
subtree_size .resize(nbNodes);
centroid_tree_distances.resize(nbNodes);
query_metadata.resize(nbNodes, inf);
for (int iR = 1; iR < nbNodes; iR ++) {
roads[A[iR]].insert({ B[iR], D[iR] });
roads[B[iR]].insert({ A[iR], D[iR] });
}
decompose(0, -1);
for (int i = 0; i < nbNodes; i ++)
reverse(centroid_tree_distances[i].begin(), centroid_tree_distances[i].end());
}
num Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i ++) enable(X[i]);
num res = inf;
for (int i = 0; i < T; i ++)
res = min(res, query(Y[i]));
for (int i = 0; i < S; i ++) reset (X[i]);
return res;
}
/*int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> nbNodes >> nbQuery;
roads.resize(nbNodes);
centroid_tree.resize(nbNodes);
subtree_size .resize(nbNodes);
centroid_tree_distances.resize(nbNodes);
query_metadata.resize(nbNodes, inf);
for (int iR = 1; iR < nbNodes; iR ++) {
int a, b, c;
cin >> a >> b >> c;
roads[a].insert({ b, c });
roads[b].insert({ a, c });
}
decompose(0, -1);
for (int i = 0; i < nbNodes; i ++)
reverse(centroid_tree_distances[i].begin(), centroid_tree_distances[i].end());
for (int iQ = 0; iQ < nbQuery; iQ ++) {
int s, t;
cin >> s >> t;
vector<int> S(s);
for (int iS = 0; iS < s; iS ++) cin >> S[iS];
for (int vS : S) enable(vS);
num res = inf;
for (int iT = 0; iT < t; iT ++) {
int vT; cin >> vT;
res = min(res, query(vT));
}
cout << res << endl;
for (int vS : S) reset (vS);
}
}*/
