0_0_23318365_16133.cpp:1:2049: fatal error: GCC4.9.2/x86_64-w64-mingw32/include/c++/bits/stdc++.h>usin: Invalid argument
/*hdu6074[并查集+LCA+思维] 2017多校4*/#include <bits/stdc++.h>using namespace std;typedef long long LL;struct node {int a, b, c, d;LL w;bool operator < (node& x) {return w < x.w;}} q[100005];vector<int> G[100005];int T, m, n;int up[100005], p[100005], deep[100005], anc[100005][22];LL cnt[100005], cost[100005];void init() {for (int i = 0; i <= n; i++) {G[i].clear();}memset(deep, 0, sizeof(deep));for (int i = 0; i <= n; i++) cost[i]=0,cnt[i]=1,p[i] = up[i] = i;}int getfa(int x) {return p[x] == x ? x : p[x] = getfa(p[x]);}int getup(int x) {return up[x] == x ? x : up[x] = getup(up[x]);}void dfs(int u, int fa) {anc[u][0] = fa;for (int i = 1; i < 21; i++) {anc[u][i] = anc[anc[u][i - 1]][i - 1];}for (int i = 0; i < (int)G[u].size(); i++) {int v = G[u][i];if (v == fa) continue;deep[v] = deep[u] + 1;dfs(v, u);}}int lca(int u, int v) {if (deep[u] < deep[v]) swap(u, v);for (int i = 21; ~i; i--) {if (deep[v] <= deep[anc[u][i]]) {u = anc[u][i];}}if (u == v) return u;for (int i = 21; ~i; i--) {if (anc[u][i] != anc[v][i]) {u = anc[u][i];v = anc[v][i];}}return anc[u][0];}void merge(int u, int v, LL w) {int x = getfa(u);int y = getfa(v);if (x == y) return; p[x] = y;cnt[y] += cnt[x];cost[y] += cost[x] + w;}void jump(int u, int v, LL w) {for (;;) {u = getup(u);if (deep[u] <= deep[v]) return;merge(u, anc[u][0], w);up[u] = anc[u][0];}}void solve() {dfs(1, 1);sort(q + 1, q + m + 1);for (int i = 1; i <= m; i++) {int k = lca(q[i].a, q[i].b);//cout << q[i].w << endl;jump(q[i].a, k, q[i].w);jump(q[i].b, k, q[i].w);k = lca(q[i].c, q[i].d);jump(q[i].c, k, q[i].w);jump(q[i].d, k, q[i].w);merge(q[i].a, q[i].c, q[i].w);}printf("%lld %lld\n",cnt[getfa(1)],cost[getfa(1)]);}int main() {scanf("%d", &T);while (T--) {int u, v;scanf("%d%d", &n, &m);init();for (int i = 1; i < n; i++) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}for (int i = 1; i <= m; i++) {scanf("%d%d%d%d%lld", &q[i].a, &q[i].b, &q[i].c, &q[i].d, &q[i].w);}solve();}return 0;}/* 3 2 3 4 5 6 7 8 9 10 4 2 5 20 10 8 10 40 6 3 1 50 1 2 3 4 5 6 7 8 9 10 7 9 10 20*/
^
compilation terminated.
|
