結果
| 問題 |
No.1424 Ultrapalindrome
|
| コンテスト | |
| ユーザー |
 stoq
|
| 提出日時 | 2021-03-13 08:24:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,953 bytes |
| コンパイル時間 | 2,886 ms |
| コンパイル使用メモリ | 217,104 KB |
| 最終ジャッジ日時 | 2025-01-19 16:04:11 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 WA * 9 |
ソースコード
#define MOD_TYPE 1
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#if 0
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif
#if 1
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
constexpr double PI = acos(-1.0);
constexpr double EPS = 1e-7;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};
#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";
struct io_init
{
io_init()
{
cin.tie(0);
ios::sync_with_stdio(false);
cout << setprecision(30) << setiosflags(ios::fixed);
};
} io_init;
template <typename T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
inline ll CEIL(ll a, ll b)
{
return (a + b - 1) / b;
}
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val)
{
fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept
{
is >> p.first >> p.second;
return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept
{
os << p.first << " " << p.second;
return os;
}
#pragma endregion
template <typename T = ll>
struct Tree
{
int V;
using P = pair<int, ll>;
vector<vector<P>> E;
vector<int> par;
vector<int> depth;
vector<int> sub;
vector<T> dist;
vector<vector<int>> par_double;
Tree(int V_) : V(V_)
{
E.resize(V);
depth.resize(V);
dist.resize(V);
sub.resize(V);
}
void add_E(int a, int b, T w = T(1), bool direction = false)
{
E[a].push_back(make_pair(b, w));
if (!direction)
E[b].push_back(make_pair(a, w));
}
int dfs(int p, int d, T w)
{
sub[p] = 1;
for (auto pi : E[p])
{
int v = pi.first;
if (par[p] == v)
continue;
par[v] = p;
depth[v] = d + 1;
dist[v] = w + pi.second;
sub[p] += dfs(v, depth[v], dist[v]);
}
return sub[p];
}
void make_tree(int root = 0)
{
calculated = false;
par.assign(V, -1);
par_double.assign(V, vector<int>(25));
depth[root] = 0;
dist[root] = T(0);
dfs(root, 0, 0);
}
bool calculated;
void calc_double()
{
for (int i = 0; i < V; i++)
par_double[i][0] = par[i];
for (int k = 0; k < 24; k++)
{
for (int i = 0; i < V; i++)
{
if (par_double[i][k] == -1)
par_double[i][k + 1] = -1;
else
par_double[i][k + 1] = par_double[par_double[i][k]][k];
}
}
}
int getLCA(int a, int b)
{
if (!calculated)
{
calc_double();
calculated = true;
}
if (a == b)
return a;
if (depth[a] < depth[b])
swap(a, b);
for (int k = 24; k >= 0; k--)
{
if (par_double[a][k] != -1 && depth[par_double[a][k]] >= depth[b])
a = par_double[a][k];
}
if (a == b)
return a;
for (int k = 24; k >= 0; k--)
{
if (par_double[a][k] != -1 && par_double[a][k] != par_double[b][k])
{
a = par_double[a][k];
b = par_double[b][k];
}
}
return par_double[a][0];
}
int length(int a, int b)
{
return depth[a] + depth[b] - 2 * depth[getLCA(a, b)];
}
int distance(int a, int b)
{
return dist[a] + dist[b] - 2 * dist[getLCA(a, b)];
}
T diameter(int &a, int &b)
{
T Max(-1);
for (int i = 0; i < V; i++)
{
if (Max < distance(0, i))
Max = distance(0, i), a = i;
}
for (int i = 0; i < V; i++)
{
if (Max < distance(a, i))
Max = distance(a, i), b = i;
}
return Max;
}
T diameter()
{
int a, b;
return diameter(a, b);
}
int diameter_l(int &a, int &b)
{
int Max = -1;
for (int i = 0; i < V; i++)
{
if (Max < length(0, i))
Max = length(0, i), a = i;
}
for (int i = 0; i < V; i++)
{
if (Max < length(a, i))
Max = length(a, i), b = i;
}
return Max;
}
int diameter_l()
{
int a, b;
return diameter_l(a, b);
}
};
void solve()
{
int n;
cin >> n;
Tree<int> tr(n);
vector<int> cnt(n, 0);
rep(i, n - 1)
{
int a, b;
cin >> a >> b, a--, b--;
cnt[a]++, cnt[b]++;
tr.add_E(a, b);
}
vector<int> leaves;
rep(i, n)
{
if (cnt[i] == 1)
{
leaves.push_back(i);
}
}
if (leaves.size() == 2)
{
Yes(1);
return;
}
tr.make_tree(leaves[0]);
int d = tr.depth[leaves[1]];
if (d % 2 == 1)
{
Yes(0);
return;
}
int v = leaves[1];
rep(i, d / 2) v = tr.par[v];
for (auto l : leaves)
{
if (tr.distance(l, v) != d / 2)
{
Yes(0);
return;
}
}
Yes(cnt[v] == n - 1);
}
int main()
{
solve();
}