Miku

一眼就看出来是个二分答案

二分最大边的权值

然后显然这种题是不需要考虑花了多少钱的，那么对于每一个mid

就先把所有范围内1级边全键了，然后再把剩下的二级边全键了，看一下能不能跑出来一个生成树

就行了

//二分解决最大的最小 
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int l,r;
int n,k,m;
int a,b;
int use1[80001];
int use2[80001];
struct e{
    int f;
    int to;
    int ne;
    int co;
    int id;
}e1[80001],e2[80001];
int head1[80001],head2[80001];
int fa[80001];
int p1,p2;
int c1,c2;
int mid;
int read(){
    int v=0;
    char c;
    int f=1;
    c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-'){
            f=-1;
        }
        c=getchar();
    }
    while('0'<=c&&c<='9'){
        v=v*10+c-'0';
        c=getchar();
    }
    return v*f;
}
void add1(int f,int to,int v,int id){
    p1++;
    e1[p1].co=v;
    e1[p1].f=f;
    e1[p1].id=id;
    e1[p1].to=to;
    e1[p1].ne=head1[f];
    head1[f]=p1;
    return ;
}
int find(int x){
    return x==fa[x] ? x:fa[x]=find(fa[x]);
}
bool com(int x,int y){
    if(find(x)!=find(y)){
        fa[find(x)]=find(y);
        return 1;
    }
    return 0;
}
void add2(int f,int to,int v,int id){
    p2++;
    e2[p2].co=v;
    e2[p2].id=id;
    e2[p2].f=f;
    e2[p2].to=to;
    e2[p2].ne=head2[f];
    head2[f]=p2;
    return ;
}
bool cmp(e x,e y){
    return x.co<y.co;
}
bool check(int li){
    int cnt=0;
    for(int i=1;i<=n;++i)
    fa[i]=i;
    for(int i=1;i<m;++i){
        if(e1[i].co>li)
        break;
        if(com(e1[i].to,e1[i].f)){
        cnt++; 
//      e1[i].id=l;
        use1[e1[i].id]=l;
        } 
        if(cnt==n-1)
        break;
    } 
    if(cnt<k)
    return 0;
    for(int i=1;i<m;++i){
        if(e2[i].co>li)
        break;
        if(com(e2[i].to,e2[i].f)){
        cnt++; 
        use2[e2[i].id]=l;
//      e2[i].id=l;
        } 
        if(cnt==n-1)
        return 1;
    }
    return 0;
}
int main(){
    n=read();
    k=read();
    m=read();
    for(int i=1;i<m;++i){
        a=read();b=read();
        c1=read();c2=read();
        add1(a,b,c1,i*2-1);
        add2(a,b,c2,i*2);
    }
    sort(e1+1,e1+m+1,cmp);
    sort(e2+1,e2+m+1,cmp);
    l=e1[k].co;
    r=max(e1[m].co,e2[m].co);
    while(l<=r){
        mid=l+(r-l)/2; 
        if(check(mid)){
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    check(l);
    cout<<l<<endl;
    for (int i=1;i<m;++i){
        if(use1[i*2-1]==l){
            printf("%d 1n",i);
        }else{
            if(use2[i*2]==l){
            printf("%d 2n",i);
        }
        }
    }
    return 0;
}