#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
#define ckif(a, b, c) ((c) ? (a) : (b))
const int MAX_N = 2e5+69;
const ll MOD = 1000000007;
const ll INF = 1e18;
int n, m;
vector<int> adj[MAX_N];
int anc[MAX_N][20], dep[MAX_N], vis[MAX_N];
pii mx[MAX_N], mx2[MAX_N];
pair<int, pii> diam[MAX_N];
bool dfs(int curr, int par = -1){
vis[curr] = 1, mx[curr] = {0, curr};
for(auto x : adj[curr]){
if(x == par) continue;
if(vis[x]) return false;
anc[x][0] = curr;
dep[x] = dep[curr]+1;
if(!dfs(x, curr)) return false;
if(mx[x].ff+1 >= mx[curr].ff) mx2[curr] = mx[curr], mx[curr] = mx[x], mx[curr].ff++;
else if(mx[x].ff+1 >= mx2[curr].ff) mx2[curr] = mx[x], mx2[curr].ff++;
if(diam[x].ff >= diam[curr].ff) diam[curr] = diam[x];
}
if(mx[curr].ff+mx2[curr].ff >= diam[curr].ff) diam[curr] = {mx[curr].ff+mx2[curr].ff, {mx[curr].ss, mx2[curr].ss}};
return true;
}
int lca(int a, int b){
if(dep[a] > dep[b]) swap(a, b);
F0Rd(i, 20) if(dep[a]+(1 << i) <= dep[b])
b = anc[b][i];
if(a == b) return a;
F0Rd(i, 20) if(anc[a][i] != anc[b][i])
a = anc[a][i], b = anc[b][i];
return anc[a][0];
}
int dist(int a, int b){
return dep[lca(a, b)]*2-dep[a]-dep[b];
}
int main(int argc, const char * argv[]){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> m;
F0R(i, m){
int a, b; cin >> a >> b; a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
if(!dfs(0)){
cout << "NO\n";
return 0;
}
FOR(d, 1, 20) F0R(i, n)
anc[i][d] = anc[anc[i][d-1]][d-1];
int a = diam[0].ss.ff, b = diam[0].ss.ss, c = lca(a, b);
F0R(i, n){
int x = c^lca(a, i)^lca(b, i);
if(dist(i, x) > 2){
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
11096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
