C++ 解法, 执行用时: 24ms, 内存消耗: 7040KB, 提交时间: 2020-10-29

#include <bits/stdc++.h>
#define ll long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define bep(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define debug cout << "KKK" << endl
#define ls num*2
#define rs num*2+1
#define re return 0
using namespace std;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const ll INF = 4e18+1;
const int inf = 1e9 + 15;
const double eps = 1e-7;
const int maxn = 1e5 + 5;
struct node{
    int v, next;
}p[maxn*2];
int ne[maxn], tot, dep[maxn];
void add(int u, int v){
    p[++tot] = (node){v, ne[u]};
    ne[u] = tot;
}
bool vis[maxn];
void dfs(int now, int pre){
    vis[now] = 1;
    dep[now] = dep[pre] + 1;
    for(int i = ne[now]; i; i = p[i].next){
        int v = p[i].v;
        if(vis[v]) continue;
        dfs(v, now);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    rep(i, 2, n){
        int u, v; cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    ll tot = 0, ma = 0;
    rep(i, 1, n){
        tot += dep[i];
        ma = max((ll)dep[i], ma);
    }
    cout << (n-1)*2 - ma + 1 << endl;
    re;
}

C++ 解法, 执行用时: 24ms, 内存消耗: 7100KB, 提交时间: 2020-07-28

#include <bits/stdc++.h>
#define ll long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define bep(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
#define debug cout << "KKK" << endl
#define ls num*2
#define rs num*2+1
#define re return 0
using namespace std;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const ll INF = 4e18+1;
const int inf = 1e9 + 15;
const double eps = 1e-7;
const int maxn = 1e5 + 5;
struct node{
    int v, next;
}p[maxn*2];
int ne[maxn], tot, dep[maxn];
void add(int u, int v){
    p[++tot] = (node){v, ne[u]};
    ne[u] = tot;
}
bool vis[maxn];
void dfs(int now, int pre){
    vis[now] = 1;
    dep[now] = dep[pre] + 1;
    for(int i = ne[now]; i; i = p[i].next){
        int v = p[i].v;
        if(vis[v]) continue;
        dfs(v, now);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    rep(i, 2, n){
        int u, v; cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    ll tot = 0, ma = 0;
    rep(i, 1, n){
        tot += dep[i];
        ma = max((ll)dep[i], ma);
    }
    cout << (n-1)*2 - ma + 1 << endl;
    re;
}