0_0_33274379_25020.c:1:1794: fatal error: cstdio: No such file or directory
#include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 2500 + 10; 8 9 int n; 10 11 struct Edge 12 { 13 int u, v, nxt; 14 bool del; 15 }; 16 17 Edge edges[maxn * 2]; 18 int ecnt; 19 int head[maxn]; 20 21 void AddEdge(int u, int v) 22 { 23 Edge& e = edges[ecnt]; 24 e.u = u; 25 e.v = v; 26 e.nxt = head[u]; 27 e.del = false; 28 head[u] = ecnt++; 29 } 30 31 int pre[maxn]; 32 int len, id; 33 void dfs(int u, int fa, int dep) 34 { 35 pre[u] = fa; 36 if(dep > len) { len = dep; id = u; } 37 for(int i = head[u]; ~i; i = edges[i].nxt) 38 { 39 if(edges[i].del) continue; 40 int v = edges[i].v; 41 if(v == fa) continue; 42 dfs(v, u, dep + 1); 43 } 44 } 45 46 int mid; 47 48 int diameter(int u) 49 { 50 id = u; 51 len = 0; 52 dfs(u, 0, 0); 53 int s = id; 54 len = 0; 55 dfs(s, 0, 0); 56 57 mid = id; 58 for(int i = 0; i < len / 2; i++) mid = pre[mid]; 59 60 return len; 61 } 62 63 int main() 64 { 65 int T; scanf("%d", &T); 66 while(T--) 67 { 68 scanf("%d", &n); 69 memset(head, -1, sizeof(head)); 70 ecnt = 0; 71 72 for(int u, v, i = 1; i < n; i++) 73 { 74 scanf("%d%d", &u, &v); 75 AddEdge(u, v); AddEdge(v, u); 76 } 77 78 int ans = 10000000; 79 int del_u, del_v, add_u, add_v; 80 81 for(int i = 0; i < ecnt; i += 2) 82 { 83 Edge& e = edges[i]; 84 edges[i].del = true; 85 edges[i^1].del = true; 86 87 int d1 = diameter(e.u), tu = mid; 88 int d2 = diameter(e.v), tv = mid; 89 int d3 = (d1 + 1) / 2 + (d2 + 1) / 2 + 1; 90 91 d1 = max(max(d1, d2), d3); 92 if(d1 < ans) 93 { 94 ans = d1; 95 del_u = edges[i].u; 96 del_v = edges[i].v; 97 add_u = tu; 98 add_v = tv; 99 } 100 101 edges[i].del = false; 102 edges[i^1].del = false; 103 } 104 105 printf("%d\n%d %d\n%d %d\n", ans, del_u, del_v, add_u, add_v); 106 } 107 108 return 0; 109 }
^
compilation terminated.
|
