結果
問題 | No.1424 Ultrapalindrome |
ユーザー |
![]() |
提出日時 | 2021-03-12 22:06:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 47 ms / 2,000 ms |
コード長 | 1,118 bytes |
コンパイル時間 | 1,773 ms |
コンパイル使用メモリ | 175,740 KB |
実行使用メモリ | 15,360 KB |
最終ジャッジ日時 | 2024-10-14 16:17:01 |
合計ジャッジ時間 | 3,370 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for(int i = 0; i < n; i++) using namespace std; typedef long long ll; const int INF = 1 << 30; const ll LLINF = 1LL << 60; int mod = 1000000007; set<int> st; vector<int> nodes[100100]; void dfs(int p, int s, int depth){ bool is_leaf = true; for(auto to: nodes[s]){ if(to == p) continue; is_leaf = false; dfs(s, to, depth+1); } if(is_leaf) st.insert(depth); return; } int main(void){ ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; rep(i, N-1){ int a, b; cin >> a >> b; a--; b--; nodes[a].push_back(b); nodes[b].push_back(a); } vector<int> jisuu_cnt(N, 0); int root = -1; rep(i, N){ jisuu_cnt[nodes[i].size()]++; if(nodes[i].size() >= 3) root = i; } if(jisuu_cnt[1]+jisuu_cnt[2] < N-1) cout << "No" << endl; else if(jisuu_cnt[1]+jisuu_cnt[2] == N) cout << "Yes" << endl; else{ dfs(-1, root, 0); if(st.size() == 1) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }