【题意】给定一个联通图，求这个图的最小生成树的不可替代边有哪些,并计算这些边的总权值。

【分析】先任意求出一颗生成树，然后标记树边和非树边。然后枚举一下非树边，对于每条边u,v，去找MST上从u到v的路径上是否存在某条边的权值等于这条边的权值。如果有，说明是可替代的。这里直接暴力u,v之间的路径或者求lca即可。

【AC 代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn = 550;
const int maxm = 50050;
struct node1{
    int u,v,w;
    int vis;
    bool operator<(const node1 &rhs)const{
        return w<rhs.w;
    }
}E1[maxm];
int head[maxn],fa[maxn],dep[maxn],tot,mst,n,m;
struct node2{
    int u,v,w,next;
    int vis;
}E2[maxm];
void init(){
    memset(head,-1,sizeof(head));tot=0;
}
void addedge(int u,int v,int w){
    E2[tot].vis=0;
    E2[tot].u=u,E2[tot].v=v,E2[tot].w=w,E2[tot].next=head[u],head[u]=tot++;
}
int Find(int x){
    if(x==fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
void Kruskal(){
    for(int i=1; i<=n; i++) fa[i]=i;
    mst=0;int num=0;
    for(int i=1; i<=m; i++){
        int u=E1[i].u,v=E1[i].v;
        int fx=Find(u),fy=Find(v);
        if(fx!=fy){
            fa[fx]=fy;
            addedge(u,v,E1[i].w);
            addedge(v,u,E1[i].w);
            num++;
            E1[i].vis=1;
            mst+=E1[i].w;
        }
        if(num==n-1) break;
    }
}
//处理dep
void dfs1(int u,int f,int d)
{
    dep[u]=d;
    for(int i=head[u]; ~i; i=E2[i].next){
        int v=E2[i].v;
        if(v==f) continue ;
        dfs1(v,u,d+1);
    }
}
//暴力LCA
void dfs2(int u,int v,int w)
{
    if(u==v) return ;
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=head[u]; ~i; i=E2[i].next){
        int to=E2[i].v;
        if(to==u) return ;
        if(dep[u]<dep[to]) continue;
        if(E2[i].w==w){
            E2[i].vis=E2[i^1].vis=1;
        }
        dfs2(to,v,w);
    }
}
int main()
{
    int u,v,w;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1; i<=m; i++){
            scanf("%d%d%d",&u,&v,&w);
            E1[i].u=u,E1[i].v=v,E1[i].w=w,E1[i].vis=0;
        }
        init();
        sort(E1+1,E1+m+1);
        Kruskal();
        dfs1(1,0,1);
        //枚举非树边
        for(int i=1; i<=m; i++){
            if(!E1[i].vis){
                dfs2(E1[i].u,E1[i].v,E1[i].w);
            }
        }
        int ans=0;
        for(int i=0; i<tot; i+=2){
            if(E2[i].vis){
                mst-=E2[i].w;
            }
            else{
                ans++;
            }
        }
        printf("%d %d\n",ans,mst);
    }
    return 0;
}