fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void dfs(int v, vector <vector <int> > &g, vector <bool> &u, vector <int> &p, vector <int> &dp) {
  5.   u[v] = 1;
  6.   for (int to: g[v]) {
  7.     if (u[to]) {
  8.       continue;
  9.     }
  10.     p[to] = v;
  11.     dfs(to, g, u, p, dp);
  12.     dp[v] = max(dp[v], dp[to] + 1);
  13.   }
  14. }
  15.  
  16. void dfs2(int v, vector <vector <int> > &g, vector <bool> &u, vector <int> &p, vector <int> &dp, vector <int> &dp_up) {
  17.   u[v] = 1;
  18.   if (p[v] != -1) {
  19.     int u = p[v];
  20.     dp_up[v] = dp_up[u] + 1;
  21.     for (int to: g[u]) {
  22.       if (p[u] != to && to != v) {
  23.         dp_up[v] = max(dp_up[v], dp[to] + 2);
  24.       }
  25.     }
  26.   }
  27.   for (int to: g[v]) {
  28.     if (!u[to]) {
  29.       dfs2(to, g, u, p, dp, dp_up);
  30.     }
  31.   }
  32. }
  33. const int M = 1e9 + 7;
  34. void solve() {
  35.   int n;
  36.   cin >> n;
  37.   vector <vector <int> > g(n);
  38.   for (int i = 1; i < n; ++i) {
  39.     int x, y;
  40.     cin >> x >> y;
  41.     --x, --y;
  42.     g[x].push_back(y);
  43.     g[y].push_back(x);
  44.   }
  45.   for (int i = 0; i < n; ++i) {
  46.     if (g[i].size() > 3) {
  47.       cout << -1 << endl;
  48.       return;
  49.     }
  50.   }
  51.   vector <int> dp(n), p(n, -1);
  52.   vector <bool> u(n);
  53.   dfs(0, g, u, p, dp);
  54.   vector <int> dp_up(n);
  55.   u.assign(n, 0);
  56.   dfs2(0, g, u, p, dp, dp_up);
  57.   int ans_h = 1000000000, ans_v = -1;
  58.   for (int i = 0; i < n; ++i) {
  59.     if (g[i].size() > 2) {
  60.       continue;
  61.     }
  62.     int h = max(dp[i], dp_up[i]);
  63.     if (ans_h > h) {
  64.       ans_h = h;
  65.       ans_v = i;
  66.     }
  67.   }
  68.   int ans = 1;
  69.   for (int i = 0; i <= ans_h; ++i) {
  70.     ans *= 2;
  71.     ans %= M;
  72.   }
  73.   ans+= M - 1;
  74.   ans %= M;
  75.   ans += M - n;
  76.   ans %= M;
  77.   cout << ans_v + 1 << ' ' << ans << endl;
  78.   return;
  79. }
  80.  
  81. int main() {
  82.   ios_base::sync_with_stdio(0);
  83.   cin.tie(0);
  84.   int T;
  85.   cin >> T;
  86.   while (T-- > 0) {
  87.     solve();
  88.   }
  89. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/i0WGaW
language:
C++14 (gcc 8.3)
created:
8 years 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!