Submission #91780

#	Time	Username	Problem	Language	Result	Execution time	Memory
91780		ngot23	Network (BOI15_net)	C++11	100 / 100	727 ms	49956 KiB

net

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define PB push_back
#define pii pair<int,int>
#define F first
#define S second
#define Task "net"
using namespace std;
const int N=500005;
int n, leaf[N], dem, cnt, s[N], deg[N], root;
vector <int > g[N];
vector <pii > ans;

void setup() {
    cin >> n;
    rep(i, 2, n) {
        int u, v; cin >> u >> v;
        g[u].PB(v); g[v].PB(u);
        ++deg[u]; ++deg[v];
    }
}

void DFS(int u, int prv) {
    bool check=1;
    for(int v:g[u]) {
        if(v==prv) continue;
        check=0;
        DFS(v, u);
    }
    if(check) leaf[++dem]=u;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    setup();
    rep(i, 1, n) {
        if(deg[i]>1) { root=i; break; }
    }
    DFS(root, 0);
    rep(i, 1, dem) {
        s[++cnt]=leaf[i];
        if(cnt>2) {
            ans.PB(mp(s[cnt-2], s[cnt]));
            s[cnt-2]=s[cnt-1];
            cnt-=2;
        }
    }
    if(cnt==2) ans.PB(mp(s[1], s[2]));
    else ans.PB(mp(s[1], root));
    cout << ans.size() << '\n';
    for(auto P:ans) {
        cout << P.F << ' ' << P.S << '\n';
    }
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37