用取反的方法来处理两个环相交的情况,,,

妙啊, 妙啊

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 1e5 + 10;inline int read(){ char ch = getchar(); int x = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x;}struct edge{ int to, cost, rev;};int N, K;vector
          
            g[MAXN];int dis[MAXN]; bool vis[MAXN];void dfs(int u, int dep) { if(vis[u]) return ; vis[u] = true; dis[u] = dep; for(int i = 0; i < (int) g[u].size(); i++) { edge &e = g[u][i]; dfs(e.to, dep + e.cost); }}bool give_tag(int u, int tag, int fa) { if(u == tag) return true; for(int i = 0; i < (int) g[u].size(); i++) { edge &e = g[u][i]; if(e.to == fa) continue; if(give_tag(e.to, tag, u)) { e.cost = g[e.to][e.rev].cost = -1; return true; } } return false;}int len = 0;void dp(int u) { vis[u] = true; for(int i = 0; i < (int) g[u].size(); i++) { edge &e = g[u][i]; if(vis[e.to]) continue; dp(e.to); len = max(len, dis[u] + dis[e.to] + e.cost); dis[u] = max(dis[u], dis[e.to] + e.cost); }}int main(){ // freopen("p3629.in", "r", stdin); cin>>N>>K; for(int i = 1; i < N; i++) { int u = read(), v = read(); g[u].push_back((edge){v, 1, g[v].size()}), g[v].push_back((edge){u, 1, g[u].size() - 1}); } dfs(1, 0); int ans = 0, st = 1, ed = 1; for(int i = 1; i <= N; i++) if(dis[i] > ans) ans = dis[i], st = i; memset(dis, 0, sizeof(dis)), memset(vis, false, sizeof(vis)); dfs(st, 0); ans = 0; for(int i = 1; i <= N; i++) if(dis[i] > ans) ans = dis[i], ed = i; if(K == 1) return printf("%d\n", ((N - 1) << 1) - ans + 1), 0; give_tag(st, ed, st); memset(dis, 0, sizeof(dis)), memset(vis, false, sizeof(vis)); dp(1); printf("%d\n", (N << 1) - ans - len); return 0;}