TOI12: Weak Point

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

vector<int> adj[N];
int dp[N], low[N], disc[N];
bool visited[N], isArt[N];

int discCnt = 0;
int DFS(int u, int p){
    visited[u] = true;
    disc[u] = ++discCnt;
    low[u] = disc[u];
    int cntArt = 1;
    int cntRet = 1;
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        if(visited[v]){
            low[u] = min(low[u], disc[v]);
        } else {
            int add = DFS(v, u);
            cntRet += add;
            low[u] = min(low[u], low[v]);
            if(p != 0 && low[v] >= disc[u]){
                cntArt += add;
                dp[u] = cntArt;
                isArt[u] = true;
            }
        }
    }
    return cntRet;
}

int main(){

    int nVertex, rt;
    scanf("%d%d", &nVertex, &rt);
    for(int i = 1; i <= nVertex; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    DFS(rt, 0);
    int weak = 0;
    int mx = 0;
    bool found = false;
    for(int u = 1; u <= nVertex; ++u){
        //printf("dp[%d]:%d\n", u, dp[u]);
        if(isArt[u] && dp[u] > mx){
            found = true;
            mx = dp[u];
            weak = u;
        }
    }
    if(found){
        cout << weak << '\n' << mx - 1;
    } else if(rt == 1){
        cout << "2\n0";
    } else {
        cout << "1\n0";
    }

    return 0;
}