結果
問題 | No.806 木を道に |
ユーザー |
![]() |
提出日時 | 2019-03-26 23:24:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 760 bytes |
コンパイル時間 | 1,980 ms |
コンパイル使用メモリ | 169,104 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2024-10-11 01:37:43 |
合計ジャッジ時間 | 4,745 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;using Pi = pair<int, int>;using Pii = pair<int, Pi>;using vint = vector<int>;int N;vint G[100010];int far[100010];int far_idx[100010];int cost[100010];void dfs(int u, int p) {far[u] = 0;far_idx[u] = u;for(int v : G[u]) {if(v == p) continue;dfs(v, u);if(far[u] < far[v]+1) {far[u] = far[v] + 1;far_idx[u] = far_idx[v];}}cost[u] = 0;for(int v : G[u]) {if(v == p) continue;cost[u] += cost[v] + (far_idx[v]!=far_idx[u]);}}int main() {cin >> N;for(int i = 0; i < N-1; ++i) {int a, b;cin >> a >> b;--a, --b;G[a].push_back(b);G[b].push_back(a);}dfs(0, -1);cout << cost[0] - (G[0].size()>1) << endl;}