真的没有人会用vector吗QwQ

思路就是在第一次边权均为正的时候用dfs算直径，有负边权了用树形dp

改边权应该没问题

#include <bits/stdc++.h>
using namespace std;
int n,k,zj[100005],ll[100005],dp[100005],d,maxpath[100005];
vector<pair<int,int> > ve[100005];

int dfs(int x,int fa){
	int len=ve[x].size();
	if(len==0) return 0;
	int max1=0,max2=0;
	for(int i=0;i<len;i++){
		if(ve[x][i].first==fa) continue;
		int an=dfs(ve[x][i].first,x)+ve[x][i].second;
		if(an>max1){
			max2=max1;
			max1=an;
		}
		else if(an>max2){
			max2=an;
		}
	}
	int t=0;
	t+=max1;
	t+=max2;
	zj[x]=t;
	ll[x]=max1;
	return max1;
}
void dfs1(int u, int fa) {
    dp[u]=0;
    int len=ve[u].size();
    if(len==0) dp[u]=0;
    for(int i=0;i<len;i++){
        if(ve[u][i].first==fa) continue;
        dfs1(ve[u][i].first,u);
        d=max(d,dp[u]+dp[ve[u][i].first]+ve[u][i].second);
        dp[u]=max(dp[u],dp[ve[u][i].first]+ve[u][i].second);
    }
}
void insert(int x,int fa){
	int len=ve[x].size();
	int maxx=-1,maxplace=-1;
	for(int i=0;i<len;i++){
		if(ve[x][i].first==fa) continue;
		if(ll[ve[x][i].first]>maxx&&ve[x][i].second!=-1){
			maxx=ll[ve[x][i].first];
			maxplace=i;
		}
	}
	if(maxplace!=-1){
		ve[x][maxplace].second=-1;
		ve[ve[x][maxplace].first].erase(remove(ve[ve[x][maxplace].first].begin(),ve[ve[x][maxplace].first].end(),make_pair(x,1)),ve[ve[x][maxplace].first].end());
		ve[ve[x][maxplace].first].push_back(make_pair(x,-1));
		insert(ve[x][maxplace].first,x);
	}
}
int main(){
	cin>>n>>k;
	int u,v;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v;
		ve[u].push_back(make_pair(v,1));
		ve[v].push_back(make_pair(u,1));
	}
	dfs(1,-1);
	int maxx=0,place=0;
	for(int i=1;i<=n;i++){
		if(zj[i]>maxx) place=i;
		maxx=max(maxx,zj[i]);
	}
	if(k==1){
		cout<<2*(n-1)-maxx+1<<endl;
		return 0;
	}
	int len=ve[place].size();
	int max1=-1,max2=-1,max1place=-1,max2place=-1;
	for(int i=0;i<len;i++){
		if(ll[ve[place][i].first]>max1){
			max2=max1;
			max2place=max1place;
			max1=ll[ve[place][i].first];
			max1place=i;
		}
		else if(ll[ve[place][i].first]>max2){
			max2place=i;
			max2=ll[ve[place][i].first];
		}
	}
	if(max1>-1){
		ve[place][max1place].second=-1;
		ve[ve[place][max1place].first].erase(remove(ve[ve[place][max1place].first].begin(),ve[ve[place][max1place].first].end(),make_pair(place,1)),ve[ve[place][max1place].first].end());
		ve[ve[place][max1place].first].push_back(make_pair(place,-1));
		insert(ve[place][max1place].first,place);
	}
	if(max2>-1){
		ve[place][max2place].second=-1;
		ve[ve[place][max2place].first].erase(remove(ve[ve[place][max2place].first].begin(),ve[ve[place][max2place].first].end(),make_pair(place,1)),ve[ve[place][max2place].first].end());
		ve[ve[place][max2place].first].push_back(make_pair(place,-1));
		insert(ve[place][max2place].first,place);
	}
	
    dfs1(1,-1);
    d=max(d,0);
	cout<<2*(n-1)-maxx+1-d+1<<endl;
	return 0;
}