METO CODE 223 拉力赛

METO CODE 223 拉力赛

传送门

继续水板子题...

#include <bits/stdc++.h>
#define ll long long
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}const int maxn = 5e5 + 10;struct Edge { int to, next, c; } edge[maxn];
int cnt, head[maxn];
struct Qedge { int to, next; } qedge[maxn];
int qcnt, qhead[maxn], n, m;
int lca[maxn];
ll dep[maxn];
int par[maxn];
int temp[maxn];
bool vis[maxn];
inline void addedge(int u, int v, int c) {edge[++cnt].to = v;edge[cnt].c = c;edge[cnt].next = head[u];head[u] = cnt; 
}
inline void addqedge(int u, int v) {qedge[++qcnt].to = v;qedge[qcnt].next = qhead[u];qhead[u] = qcnt;
}
int getfa(int x) { return x == par[x] ? x : par[x] = getfa(par[x]); }void dfs(int u) {par[u] = u;vis[u] = 1; for (int i = head[u]; i; i = edge[i].next) {int v = edge[i].to;if (!vis[v]) {dep[v] = dep[u] + edge[i].c;dfs(v);par[v] = u;} }for (int i = qhead[u]; i; i = qedge[i].next) {int v = qedge[i].to;if (vis[v]) {lca[i] = getfa(v);if (i % 2) lca[i + 1] = lca[i];else lca[i-1] = lca[i];}}
}int main() {n = read(), m = read();for (int i = 0; i < n - 1; i++) {int u = read(), v =read(), c = read();addedge(u, v, c);addedge(v, u, c);} for (int i = 1; i <= m; i++) {int u = read(), v = read();addqedge(u, v), addqedge(v, u);}dfs(1);ll ans = 0;int cnt = 0;for (int i = 1; i <= m; i++) {if (lca[2 * i] == qedge[2 * i].to) {cnt++;ans += dep[qedge[2*i].to] + dep[qedge[2*i-1].to] - 2 * dep[lca[2*i]];}} printf("%dn%lldn", cnt, ans);return 0;
}

转载于:.html