求卡常
查看原帖
求卡常
639563
封禁用户楼主2024/7/4 11:14

我在洛谷过了,在某学校的校内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);
}
2024/7/4 11:14
加载中...