#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #ifndef LOCAL #define debug(x) ; #else #define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; template ostream &operator<<(ostream &out, const pair &p) { out << "{" << p.first << ", " << p.second << "}"; return out; } template ostream &operator<<(ostream &out, const vector &v) { out << '{'; for (const T &item : v) out << item << ", "; out << "\b\b}"; return out; } #endif #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 200010 /*Lowest Common Ancstor*/ struct LCA{ int n; vector> tree, parent; vector depth; int max_log; LCA(int n): n(n), tree(n), depth(n, -1) { max_log = 0; for(int i=1; i<=n*2; i*=2) max_log++; parent.assign(max_log, vector(n, -1)); } void add_edge(int u, int v) { tree[u].push_back(v); tree[v].push_back(u); } void dfs(int now, int p, int d){ parent[0][now] = p; depth[now] = d; for(int to : tree[now]) if(to != p) dfs(to, now, d+1); } void build(int root){ dfs(root, -1, 0); for(int i=0; i depth[b]) swap(a, b); for(int i=0; i> i & 1) b = parent[i][b]; if(a == b) return a; for(int i=max_log-1; i>=0; i--){ if(parent[i][a] != parent[i][b]){ a = parent[i][a]; b = parent[i][b]; } } return parent[0][a]; } }; vector> G[SIZE]; ll dist[SIZE]; int parent[18][SIZE]; int eulerIn[SIZE], eulerOut[SIZE], counter = 0; void dfs(int now, int back = -1, int d = 0) { dist[now] = d; parent[0][now] = back; eulerIn[now] = counter++; for (auto p : G[now]) { int to = p.first; int cost = p.second; if (to == back) continue; dfs(to, now, d + cost); } eulerOut[now] = counter++; } int main(){ int N, Q; scanf("%d", &N); LCA lca(N); for (int i=0; i ss; priority_queue> pq; for (int j=0; j 1) { auto p = pq.top(); pq.pop(); int x = p.second; int tmp = x; ss.erase(ss.find(eulerIn[x])); for (int j=17; j>=0; j--) { if (parent[j][tmp] == -1) continue; int q = parent[j][tmp]; auto it = ss.lower_bound(eulerIn[q]); if (it == ss.end() || eulerOut[q] < *it) tmp = q; } auto it = ss.lower_bound(eulerIn[tmp]); if (it == ss.end() || eulerOut[tmp] < *it) tmp = parent[0][tmp]; debug(x); debug(tmp); ans += dist[x] - dist[tmp]; if (ss.find(eulerIn[tmp]) == ss.end()) { pq.push({dist[tmp], tmp}); ss.insert(eulerIn[tmp]); } } printf("%lld\n", ans); } return 0; }