感觉题目都已经快把正解给说出来了...
strongly connected的两个点的消耗为0，其实就是同一个边双连通分量里面的点消耗为0。
然后缩一下点，再树形DP一下就完了。
第一次写边双，但感觉挺简单的。
#include <bits/stdc++.h>
#define ll long long
using namespace std; const int N = 4e5 + ;
int c[N];
bool bridge[N * ]; struct E {
int v, ne;
ll c;
} e[N * ], tree[N * ];
int head[N], hd[N], cnt1, cnt2;
int dfn[N], low[N], id;
int color[N]; inline void add1(int u, int v, ll c) {
e[++cnt1].v = v; e[cnt1].ne = head[u]; e[cnt1].c = c; head[u] = cnt1;
} inline void add2(int u, int v, ll c) {
tree[++cnt2].v = v; tree[cnt2].ne = hd[u]; tree[cnt2].c = c; hd[u] = cnt2;
} void tarjan(int u, int edge) {
dfn[u] = low[u] = ++id;
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (low[v] > low[u])
bridge[i] = bridge[i ^ ] = ;
} else if (i != (edge ^ ))
low[u] = min(low[u], dfn[v]);
}
} int dcc; void dfs0(int u) {
c[u] = dcc;
color[dcc] = min(color[dcc], u);
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].v;
if (c[v] || bridge[i]) continue;
dfs0(v);
}
} ll dp[N][];
int son[N][];
void dfs(int u, int fa) {
dp[u][] = dp[u][] = ;
son[u][] = son[u][] = ;
for (int i = hd[u]; i; i = tree[i].ne) {
int v = tree[i].v;
if (v == fa) continue;
dfs(v, u);
if (dp[v][] + tree[i].c > dp[u][]) {
dp[u][] = dp[u][];
son[u][] = son[u][];
dp[u][] = dp[v][] + tree[i].c;
son[u][] = v;
} else if (dp[v][] + tree[i].c > dp[u][]) {
son[u][] = v;
dp[u][] = dp[v][] + tree[i].c;
}
}
} void dfs2(int u, int fa, ll c) {
if (fa) {
if (son[fa][] != u) {
if (dp[fa][] + c > dp[u][]) {
dp[u][] = dp[u][];
son[u][] = son[u][];
dp[u][] = dp[fa][] + c;
son[u][] = fa;
} else if (dp[fa][] + c > dp[u][]) {
son[u][] = fa;
dp[u][] = dp[fa][] + c;
}
} else {
if (dp[fa][] + c > dp[u][]) {
dp[u][] = dp[u][];
son[u][] = son[u][];
dp[u][] = dp[fa][] + c;
son[u][] = fa;
} else if (dp[fa][] + c > dp[u][]) {
son[u][] = fa;
dp[u][] = dp[fa][] + c;
}
}
}
for (int i = hd[u]; i; i = tree[i].ne) {
int v = tree[i].v;
if (v == fa) continue;
dfs2(v, u, tree[i].c);
}
} int main() {
freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) {
head[i] = hd[i] = ;
c[i] = ;
low[i] = dfn[i] = ;
color[i] = n + ;
}
memset(bridge, , sizeof(bridge));
cnt1 = ;
for (int u, v, i = ; i <= m; i++) {
ll c;
scanf("%d%d%lld", &u, &v, &c);
add1(u, v, c);
add1(v, u, c);
}
id = ;
for (int i = ; i <= n; i++)
if (!dfn[i])
tarjan(i, );
dcc = ;
for (int i = ; i <= n; i++)
if (!c[i]) {
++dcc;
dfs0(i);
}
cnt2 = ;
for (int i = ; i <= cnt1; i++) {
int u = e[i ^ ].v, v = e[i].v;
if (c[u] == c[v]) continue;
add2(c[u], c[v], e[i].c);
}
memset(dp, , sizeof(dp));
dfs(, );
dfs2(, , );
int ans1 = ; ll ans2 = 1e18;
for (int i = ; i <= dcc; i++) {
if (dp[i][] < ans2) ans2 = dp[i][], ans1 = color[i];
else if (dp[i][] == ans2 && ans1 > color[i]) ans1 = color[i];
//printf("%lld\n", dp[i][0]);
}
printf("%d %lld\n", ans1, ans2);
}
return ;
}