Maison >interface Web >tutoriel HTML >Codeforces Round #260 (Div. 1)??Civilization_html/css_WEB-ITnose
题目链接
const int MAXN = 310000;int rt[MAXN], ans[MAXN];VI G[MAXN];bool vis[MAXN];void init(int n){ REP(i, n) { vis[i] = false; ans[i] = 0; G[i].clear(); rt[i] = i; }}int find(int n){ return n == rt[n] ? n : rt[n] = find(rt[n]);}void merge(int a, int b){ int fa = find(a), fb = find(b); if (fa != fb) { rt[fa] = fb; ans[fb] = max(ans[fb], (ans[fb] + 1) / 2 + (ans[fa] + 1) / 2 + 1); ans[fb] = max(ans[fa], ans[fb]); }}int Max, id;void dfs(int u, int fa, int dep){ vis[u] = true; REP(i, G[u].size()) { int v = G[u][i]; if (v != fa) dfs(v, u, dep + 1); } if (dep > Max) { Max = dep; id = u; }}int main(){ int n, m, q; while (~RIII(n, m, q)) { init(n + 1); REP(i, m) { int a, b; RII(a, b); G[a].push_back(b); G[b].push_back(a); int fa = find(a), fb = find(b); rt[fa] = fb; } FE(i, 1, n) { if (!vis[i]) { Max = -1; dfs(i, -1, 0); Max = -1; dfs(id, -1, 0); ans[find(i)] = Max; } } REP(i, q) { int op; RI(op); if (op == 2) { int a, b; RII(a, b); merge(a, b); } else { int a; RI(a); WI(ans[find(a)]); } } } return 0;}