Submission #1132561


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int md = 1000000007;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) {
    a -= md;
  }
}

inline int mul(int a, int b) {
  return (long long) a * b % md;
}

const int N = 2010;

int depth[N];
vector <int> g[N], new_g[N];
int it, mark[N][N];
int f[N][N];
int D;

int go(int v, int pr, int x) {
  if (mark[v][x] == it) {
    return f[v][x];
  }
  mark[v][x] = it;
  f[v][x] = 1;
  int y = (D - depth[v]) - x;
//  cerr << "go " << v << " " << x << " " << y << endl;
  int sz = g[v].size();
  for (int j = 0; j < sz; j++) {
    int u = g[v][j];
    if (u == pr) {
      continue;
    }
    int cur = 0;
    if (x > 0) {
      cur = go(u, v, x - 1);
    }
    if (y > 0) {
      add(cur, go(u, v, x));
    }
    f[v][x] = mul(f[v][x], cur);
  }
  return f[v][x];
}

int curr[N][N];
int x[N], d[N];
int C[N][N];
pair <int, int> edge[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    foo--; bar--;
    edge[i] = make_pair(foo, bar);
    g[foo].push_back(bar);
    g[bar].push_back(foo);
  }
  int max_deg = 0;
  for (int i = 0; i < n; i++) {
    max_deg = max(max_deg, (int) g[i].size());
  }
  if (max_deg <= 2) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (j == 0) C[i][j] = 1; else
        if (i == 0) C[i][j] = 0;
        else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
      }
    }
    int ans = C[n - 1][(n - 1) / 2];
    if (n % 2 == 0) {
      add(ans, ans);
    }
    printf("%d\n", ans);
    return 0;
  }
  int coeff = 1;
  int root;
  int another_root;
  int diam = 0;
  while (true) {
    D = (int) 1e9;
    root = -1;
    another_root = -1;
    for (int start = 0; start < n; start++) {
      for (int i = 0; i < n; i++) {
        d[i] = -1;
      }
      int b = 0, e = 1;
      x[0] = start;
      d[start] = 0;
      while (b < e) {
        int sz = g[x[b]].size();
        for (int j = 0; j < sz; j++) {
          int u = g[x[b]][j];
          if (d[u] == -1) {
            x[e] = u;
            d[u] = d[x[b]] + 1;
            e++;
          }
        }
        b++;
      }
      int rad = 0;
      for (int i = 0; i < n; i++) {
        rad = max(rad, d[i]);
      }
      diam = max(diam, rad);
      if (rad < D) {
        D = rad;
        root = start;
        another_root = -1;
        for (int i = 0; i < n; i++) {
          depth[i] = d[i];
        }
      } else {
        if (rad == D) {
          another_root = start;
        }
      }
    }
    if (diam % 2 == 0) {
      break;
    }
    coeff = mul(coeff, 2);
    break;
/*    assert(another_root != -1);
    for (int i = 0; i < n - 1; i++) {
      new_g[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int foo = edge[i].first;
      int bar = edge[i].second;
      if (foo == another_root) {
        foo = root;
      }
      if (bar == another_root) {
        bar = root;
      }
      if (foo == n - 1) {
        foo = another_root;
      }
      if (bar == n - 1) {
        bar = another_root;
      }
      new_g[foo].push_back(bar);
      new_g[bar].push_back(foo);
    }
    n--;
    for (int i = 0; i < n; i++) {
      g[i] = new_g[i];
    }*/
  }
//  cerr << "D = " << D << endl;
//  cerr << "diam = " << diam << endl;
//  cerr << "root = " << root << endl;
//  cerr << "another_root = " << another_root << endl;
  int ans = 0;
  if (diam % 2 == 0) {
    it = 0;
    for (int x = 0; x <= D; x++) {
      it++;
      int cur = go(root, another_root, x);
      add(ans, cur);
    }
  } else {
    it = 0;
    for (int x = 0; x <= D; x++) {
      for (int y = 0; x + y <= D; y++) {
        if (x + y < D - 1) {
          continue;
        }
        it++;
        bool flag = false;
        if (x + y < D) {
          D--;
          flag = true;
        }
        D++;
        int cur = go(another_root, root, x);
        curr[x][y] = cur;
        D--;
        if (flag) {
          D++;
        } else {
          if (x > 0) {
            add(cur, md - curr[x - 1][y]);
          }
          if (y > 0) {
            add(cur, md - curr[x][y - 1]);
          }
        }
//        cerr << "now cur = " << cur << endl;
        int new_x = x + 1;
        int new_y = y;
        int bound_x = D - new_y;
        int bound_y = D - new_x;
        int new_D = bound_x + bound_y;
        int old_D = D;
        D = new_D;
        cur = mul(cur, go(root, another_root, bound_x));
        add(ans, cur);
        D = old_D;
//        cerr << x << " " << y << " -> " << cur << endl;
      }
    }
  }
  printf("%d\n", mul(ans, coeff));
//  cerr << clock() << " ms" << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Oriented Tree
User tourist
Language C++14 (GCC 5.4.1)
Score 1800
Code Size 4890 Byte
Status AC
Exec Time 943 ms
Memory 22912 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
./Main.cpp:62:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &foo, &bar);
                               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1800 / 1800
Status
AC × 4
AC × 33
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt
Case Name Status Exec Time Memory
0_00.txt AC 2 ms 6528 KB
0_01.txt AC 13 ms 16768 KB
0_02.txt AC 2 ms 6528 KB
0_03.txt AC 2 ms 6528 KB
1_00.txt AC 13 ms 16768 KB
1_01.txt AC 14 ms 16768 KB
1_02.txt AC 14 ms 16768 KB
1_03.txt AC 11 ms 20864 KB
1_04.txt AC 11 ms 20864 KB
1_05.txt AC 19 ms 20864 KB
1_06.txt AC 23 ms 20864 KB
1_07.txt AC 22 ms 20864 KB
1_08.txt AC 28 ms 20864 KB
1_09.txt AC 39 ms 20864 KB
1_10.txt AC 41 ms 20864 KB
1_11.txt AC 99 ms 22912 KB
1_12.txt AC 105 ms 20864 KB
1_13.txt AC 456 ms 22912 KB
1_14.txt AC 419 ms 20864 KB
1_15.txt AC 711 ms 20864 KB
1_16.txt AC 943 ms 20864 KB
1_17.txt AC 18 ms 20864 KB
1_18.txt AC 16 ms 20864 KB
1_19.txt AC 18 ms 20864 KB
1_20.txt AC 16 ms 20864 KB
1_21.txt AC 16 ms 20864 KB
1_22.txt AC 14 ms 20864 KB
1_23.txt AC 13 ms 20864 KB
1_24.txt AC 13 ms 20864 KB
1_25.txt AC 12 ms 20864 KB
1_26.txt AC 12 ms 20864 KB
1_27.txt AC 12 ms 20864 KB
1_28.txt AC 11 ms 20864 KB