Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <string>
- #include <vector>
- #define SZ(x) ((int)(x).size())
- #define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
- using namespace std;
- typedef long long LL;
- const int N = 1e5+5;
- vector<int> a[N];
- int mark[N], mark2[N];
- int getparent(int x, int y) {
- if (SZ(a[x]) == 1) {
- return y == -1? a[x][0] : 0;
- }
- if (SZ(a[x]) == 2) {
- return y == -1? 0 : a[x][0] + a[x][1] - y;
- }
- return 0;
- }
- int main(void) {
- int n;
- scanf("%d", &n);
- for(int i=1;i<n;i++) {
- int x, y;
- scanf("%d%d", &x, &y);
- a[x].push_back(y);
- a[y].push_back(x);
- }
- for(int i=1;i<=n;i++) {
- if(SZ(a[i])==1 && mark[i]==0) {
- int x = i, y = -1, z;
- mark[x] = 1;
- while ((z = getparent(x, y)) > 0) {
- if(SZ(a[z]) > 2) break;
- mark[z] = 1;
- y = x;
- x = z;
- }
- }
- }
- int d[3]={}, ok = 1;
- for(int i=1;i<=n;i++) {
- if (mark[i]==0) {
- int deg=0;
- FOR(it, a[i]) if(mark[*it]==0) ++deg;
- if (deg==1 && SZ(a[i])<=3) mark2[i] = 1;
- }
- }
- for(int i=1;i<=n;i++) mark[i] |= mark2[i];
- for(int i=1;i<=n;i++) {
- if (mark[i]==0) {
- int deg=0;
- FOR(it, a[i]) if(mark[*it]==0) ++deg;
- if (deg<=2) ++d[deg];
- else ok=0;
- }
- }
- if(d[1]>2) ok = 0;
- puts(ok? "Yes":"No");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement