QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#62356 | #4599. Orgrimmar | qinjianbin# | AC ✓ | 1180ms | 58228kb | C++17 | 1.0kb | 2022-11-18 13:03:04 | 2022-11-18 13:03:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 10, MAXM = 1e6 + 10;
int h[MAXN], e[MAXM], ne[MAXM], idx;
void AddEdge(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
int T, n;
int dp[MAXN][3];
void dfs(int u, int fa) {
int sum0 = 0, sum = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs(v, u);
sum += max({dp[v][2], dp[v][1], dp[v][0]});
sum0 += dp[v][0];
}
dp[u][0] = sum;
dp[u][2] = sum0 + 1;
dp[u][1] = dp[u][2];
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dp[u][1] = max(dp[u][1], 1 + sum0 - dp[v][0] + dp[v][2]);
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
idx = 0;
for (int i = 1; i <= n; i++) h[i] = -1, dp[i][0] = dp[i][1] = dp[i][2] = 0;
int u, v;
for (int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
AddEdge(u, v);
AddEdge(v, u);
}
dfs(1, 0);
printf("%d\n", max({dp[1][0], dp[1][1], dp[1][2]}));
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1180ms
memory: 58228kb
input:
10 500000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...
output:
333334 499999 374859 374664 374655 374764 374530 374548 374848 374511
result:
ok 10 lines