fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Task "KPATH"
  5. #define sz(x) (int)x.size()
  6. #define bit(x, i) ((x >> i) & 1)
  7. #define sp " "
  8. #define endl "\n"
  9.  
  10. constexpr int maxn = 3e5 + 5;
  11.  
  12. int n;
  13. vector<int> g[maxn];
  14. int degcnt[maxn];
  15. int in[maxn];
  16.  
  17. bool check(vector<int> &u) {
  18.     int k = sz(u);
  19.     for(int x : u) in[x] = 1;
  20.     fill(degcnt + 1, degcnt + n + 1, 0);
  21.  
  22.     int edge = 0;
  23.  
  24.     for (auto v : u) {
  25.         for (auto to : g[v]) {
  26.             if (in[to]) {
  27.                 edge++;
  28.                 degcnt[v]++;
  29.             }
  30.         }
  31.     }
  32.     edge /= 2;
  33.  
  34.     if(k == 1) return true;
  35.     if(edge != k - 1) return false;
  36.  
  37.     int tmp = 0;
  38.  
  39.     for(int v : u) {
  40.         if(degcnt[v] == 1) tmp++;
  41.         else if(degcnt[v] == 2);
  42.         else return false;
  43.     }
  44.  
  45.            return tmp == 2;
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.  
  52.     if(fopen(Task".inp", "r")) {
  53.         freopen(Task".inp", "r", stdin);
  54.         freopen(Task".out", "w", stdout);
  55.     }
  56.  
  57.     cin >> n;
  58.  
  59.     for(int i = 1; i < n; i++) {
  60.         int u, v;
  61.         cin >> u >> v;
  62.         g[u].push_back(v);
  63.         g[v].push_back(u);
  64.     }
  65.  
  66.     for(int k = 1; k <= n; k++) {
  67.         vector<int> Pmask;
  68.         for(int mask = 0; mask < (1 << k); mask++) {
  69.             if(__builtin_popcount(mask) != k) continue;
  70.  
  71.             vector<int> cur;
  72.             for(int i = 1; i <= n; i++) {
  73.                 if(bit(mask, i)) {
  74.                     cur.push_back(i);
  75.                 }
  76.  
  77.                 if(check(cur)) {
  78.                     Pmask.push_back(mask);
  79.                 }
  80.             }
  81.         }
  82.  
  83.         int m = sz(Pmask);
  84.         int ans = 0;
  85.  
  86.         for(int mask = 0; mask < (1 << m); mask++) {
  87.             bool isValid = true;
  88.             int cnt = 0;
  89.  
  90.             for(int i = 0; i < m; i++) {
  91.                 if(bit(mask, i)) {
  92.                     if(cnt & Pmask[i]) {
  93.                         isValid = false;
  94.                         break;
  95.                     }
  96.                     cnt |= Pmask[i];
  97.                 }
  98.             }
  99.  
  100.             if(isValid) {
  101.                 ans = max(ans, (int)__builtin_popcount(mask));
  102.             }
  103.         }
  104.  
  105.         cout << ans << endl;
  106.     }
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 10928KB
comments (?)
stdin
copy 
6
1 2
2 3
2 4
1 5
5 6
stdout
copy 
0
1
1
1
1
1
https://ideone.com/mJSVSg
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!