我在洛谷过了,在某学校的校内OJ上TLE,怎么会是呢
洛谷限制:256MB/2s
学校OJ限制:192MB/1.5s
可我在洛谷上跑,最慢的点都只有700多ms,怎么会T呢
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> graph[1000005];
ll dep[1000005], sz[1000005];
void dfs0(int u, int fa = -1) {
sz[u] = 1;
for (int v : graph[u]) {
if (v != fa) {
dep[v] = dep[u] + 1;
dfs0(v, u);
sz[u] += sz[v];
}
}
}
pair<ll, int> dfs(int u, ll sum, int fa = -1) {
pair<ll, int> ans = make_pair(sum, u);
for (int v : graph[u]) {
if (v != fa) {
ans = max(ans, dfs(v, sum - sz[v] + (n - sz[v]), u));
}
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
u--, v--;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs0(0);
ll sum = 0;
for (int i = 0; i < n; i++) {
sum += dep[i];
}
printf("%d", dfs(0, sum).second + 1);
}