想法题，只需要分析一个点及其直接连通的边即可，维护一个vtot记录总和，vmax记录最大的边权，如果vmax>=vtot-2,那么一共有vmax个自行车。否则，如果vsum是偶数，剩下的边一定会匹配，如果vsum是奇数，除去一条边，剩下的一定会匹配。

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 100100using namespace std;const int inf=(~(0U))>>1;int head[N],ans,cnt,dp[N][100],cost[N][100]; //记录未匹配的vector
         
          vv;struct edge{ int u,v,w,next;}edge[N*2];void addedge(int u,int v,int w){ edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].u=v; edge[cnt].v=u; edge[cnt].w=w; edge[cnt].next=head[v]; head[v]=cnt++;}void init(){ cnt=0; memset(head,-1,sizeof(head)); ans=0;}void dfs(int u,int fa,int be){ int i,j,k,flag=0,tem,aaa=(~(0U))>>1,all=0; for(i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa) continue; dfs(v,u,edge[i].w); flag++; } if(flag==0){ return; } int vmax=be,vtot=be; for(i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa) continue; vmax=max(vmax,edge[i].w); vtot+=edge[i].w; } if(vmax>=vtot-vmax){ if(be!=vmax){ ans+=vmax-be; } } else{ ans+=(vtot+1)/2-be; }}int main(){ int t,T,n,i,u,v,w; scanf("%d",&T); for(t=1;t<=T;t++){ init(); scanf("%d",&n); for(i=1;i