- 1#include 2#include < string.h > 3#include 4 using namespace std;
- 5#define ll __int64 6 struct node 7 {
- 8 int from;
- 9 int to;
- 10 int w;
- 11 int next;
- 12
- }
- e[1500000];
- 13 int n;
- 14 int root;
- 15 int minn;
- 16 int cont;
- 17 ll output;
- 18 int vis[150000];
- 19 int d[150000];
- 20 int head[150000];
- 21 void add(int from, int to, int w) 22 {
- 23 e[cont].to = to;
- 24 e[cont].w = w;
- 25 e[cont].next = head[from];
- 26 head[from] = cont++;
- 27
- }
- 28 int Dfs(int u, int from) 29 {
- 30
- if (d[u] == 0) 31 {
- 32 d[u] = 1;
- 33
- for (int i = head[u]; i != -1; i = e[i].next) 34 {
- 35 int v = e[i].to;
- 36
- if (v == from) continue;
- 37 d[u] += Dfs(v, u);
- 38
- }
- 39 int tmpmaxn = 0;
- 40
- for (int i = head[u]; i != -1; i = e[i].next) 41 {
- 42 int v = e[i].to;
- 43 tmpmaxn = max(d[v], tmpmaxn);
- 44
- }
- 45 tmpmaxn = max(n - d[u], tmpmaxn);
- 46
- if (tmpmaxn < minn) 47 {
- 48 minn = tmpmaxn;
- 49 root = u;
- 50
- }
- 51
- }
- 52
- return d[u];
- 53
- }
- 54 int main() 55 {
- 56
- while (~scanf("%d", &n)) 57 {
- 58 cont = 0;
- 59 memset(vis, 0, sizeof(vis));
- 60 memset(d, 0, sizeof(d));
- 61 memset(head, -1, sizeof(head));
- 62
- for (int i = 0; i1; i++) 63 {
- 64 int x,
- y,
- w;
- 65 scanf("%d%d%d", &x, &y, &w);
- 66 add(x, y, w);
- 67 add(y, x, w);
- 68
- }
- 69 output = 0;
- 70 root = -1;
- 71 minn = 0x3f3f3f3f;
- 72 Dfs(1, -1);
- 73 printf("%d\n", root);
- 74
- }
- 75
- }
来源: http://www.bubuko.com/infodetail-1984973.html