看标程的代码这么短，看我的....
难道是静态LCA模板太长了？
/*
HDU 6074 - Phone Call [ LCA,并查集 ] | 2017 Multi-University Training Contest 4
题意：
给一棵树，定义集合S(u,v)为u到v路径上所有的点
给出 m 个 <S(u1,v1)|S(u2,v2) , w > ，意思为集合里面的点互相距离为 w
求 1 能到的所有点和该生成树的最小权值
分析：
将所有线路按代价从小到大排序，对于每条线路(a,b,c,d)
分别把S(a,b)和S(c,d)合并到 LCA，最后再把两个 LCA 合并即可
再用f(i)表示i向上第一个与i不在同一个连通块的点, 就可用并查集压缩路径
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100005;
const int Q = 200005;
vector<int> G[N];
namespace LCA{
struct Query {
int v, q;
}; vector <Query> query[N];
int ans[Q], f[N], vis[N];
int sf(int x) {
return x == f[x] ? x : f[x] = sf(f[x]);
}
void init() {
memset(ans, -1, sizeof(ans));
for (int i = 0; i < N; i++) {
vis[i] = 0;
f[i] = i;
query[i].clear();
}
}
void adq(int u, int v, int id) {
query[u].push_back(Query{v, id});
query[v].push_back(Query{u, id});
}
void LCA(int u) {
f[u] = u;
vis[u] = 1;
for (auto& x : query[u]) {
if (vis[x.v] && ans[x.q] == -1)
ans[x.q] = sf(x.v);
}
for (auto& v : G[u]) {
if (vis[v]) continue;
LCA(v);
f[v] = u;
}
}
}
int pre[N];
void dfs(int u, int fa) {
pre[u] = fa;
for (auto v : G[u]) {
if (v == fa) continue;
dfs(v, u);
}
}
int f[N], num[N];
LL res[N];
int sf(int x){
return x == f[x] ? x : f[x] = sf(f[x]);
}
int same[N];
int Same(int x) {
return x == same[x] ? x : same[x] = Same(same[x]);
}
int w;
void join(int a, int b){
a = sf(a), b = sf(b);
if (a == b) return;
f[b] = a;
num[a] += num[b];
res[a] += res[b] + w;
}
struct Node {
int a1, b1, a2, b2, w;
int c1, c2;
}e[N];
bool cmp(Node a, Node b) {
return a.w < b.w;
}
void solve(int a, int fa) {
while (Same(a) != Same(fa)) {
a = Same(a);
join(pre[a], a);
same[a] = pre[a];
}
}
int t, n, m;
int main() {
scanf("%d", &t);
while (t--) {
for (int i = 0; i < N; i++) G[i].clear();
LCA::init();
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int Q = 0;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d%d", &e[i].a1, &e[i].b1, &e[i].a2, &e[i].b2, &e[i].w);
e[i].c1 = ++Q;
LCA::adq(e[i].a1, e[i].b1, Q);
e[i].c2 = ++Q;
LCA::adq(e[i].a2, e[i].b2, Q);
}
LCA::LCA(1);
for (int i = 1; i <= m; i++) {
e[i].c1 = LCA::ans[e[i].c1];
e[i].c2 = LCA::ans[e[i].c2];
}
dfs(1, 1);
sort(e+1, e+m+1, cmp);
for (int i = 1; i <= n; i++) {
f[i] = same[i] = i;
num[i] = 1;
res[i] = 0;
}
for (int i = 1; i <= m; i++) {
w = e[i].w;
solve(e[i].a1, e[i].c1);
solve(e[i].b1, e[i].c1);
solve(e[i].a2, e[i].c2);
solve(e[i].b2, e[i].c2);
join(e[i].c1, e[i].c2);
}
printf("%d %lld
", num[sf(1)], res[sf(1)]);
}
}