#37698: TLE之後用的獵奇解法


samlin961112@gmail.com (林哲甫)

學校 : 新北市私立南山高級中學
編號 : 220506
來源 : [219.70.213.92]
最後登入時間 :
2024-10-21 22:34:09
b967. 4. 血緣關係 -- 2016年3月apcs | From: [219.70.213.92] | 發表日期 : 2023-09-29 20:44

#include <bits/stdc++.h>
using namespace std;
inline void fastInput(int &x) {
  x = 0;
  char c = getchar_unlocked();
  if(c=='E'){
    x=-1;
    return;
  }
  if (c < '0' || c > '9') {
    x=-1;
    return;
  }
  while (c >= '0' && c <= '9') {
    x = (x * 10) + (c - '0');
    c = getchar_unlocked();
  }
}
inline void fastOutput(int x) {
  if(x==0){
    putchar_unlocked('0');
  }
  char buffer[20];
  int idx = 0;
  while (x > 0) {
    buffer[idx++] = (x % 10) + '0';
    x /= 10;
  }
  for (int i = idx - 1; i >= 0; --i) {
    putchar_unlocked(buffer[i]);
  }
  putchar_unlocked('\n');
}
inline pair<int, int> dfs(vector<vector<int>>&p, int s, int parent) {
    int x = s;
    int m = 0;
    for (int i = 0; i < p[s].size(); i++) {
        if (p[s][i] == parent){continue;}
        pair<int, int> a = dfs(p,p[s][i], s);
        if (m < a.first + 1) {
            m = a.first + 1;
            x = a.second;
        }
    }
    return make_pair(m, x);
}

int main() {
    int n;
    while(true){
      fastInput(n);
      if(n==-1){break;}
    vector<vector<int>> p(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        fastInput(a);fastInput(b);
        p[a].push_back(b);
        p[b].push_back(a);
    }
    fastOutput( dfs(p, dfs(p, 0, -1).second, -1).first);
    }
}

 
ZeroJudge Forum