結果
問題 | No.2427 Tree Distance Two |
ユーザー |
![]() |
提出日時 | 2023-08-22 13:29:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 774 ms |
コンパイル使用メモリ | 52,812 KB |
実行使用メモリ | 28,416 KB |
最終ジャッジ日時 | 2024-12-16 10:54:17 |
合計ジャッジ時間 | 8,958 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
/* -*- coding: utf-8 -*-** 2427.cc: No.2427 Tree Distance Two - yukicoder*/#include<cstdio>#include<vector>#include<algorithm>using namespace std;/* constant */const int MAX_N = 300000;/* typedef */typedef vector<int> vi;/* global variables */vi nbrs[MAX_N];int ps[MAX_N], cis[MAX_N], ss1[MAX_N], ss2[MAX_N];int pss1[MAX_N], pss2[MAX_N];/* subroutines *//* main */int main() {int n;scanf("%d", &n);for (int i = 1; i < n; i++) {int u, v;scanf("%d%d", &u, &v);u--, v--;nbrs[u].push_back(v);nbrs[v].push_back(u);}ps[0] = -1;for (int u = 0; u >= 0;) {vi &nbru = nbrs[u];int up = ps[u];if (cis[u] < nbru.size()) {int v = nbru[cis[u]++];if (v != up) {ps[v] = u;u = v;}}else {if (up >= 0) {ss1[up]++;ss2[up] += ss1[u];}u = up;}}fill(cis, cis + n, 0);for (int u = 0; u >= 0;) {vi &nbru = nbrs[u];int up = ps[u];if (cis[u] < nbru.size()) {int v = nbru[cis[u]++];if (v != up) {pss1[v] = 1;pss2[v] = ss1[u] - 1 + pss1[u];u = v;}}else {u = up;}}for (int u = 0; u < n; u++) printf("%d\n", ss2[u] + pss2[u]);return 0;}