Submission #1135966


Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

typedef long double ld;
typedef long long ll;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define pb push_back
#define mp make_pair
#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);

const int mod = (int) 1e9 + 7;

void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int mult(int x, int y) {
  return (long long) x * y % mod;
}

int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}

void precalc() {
}

const int maxn = (int) 1e3 + 10;
int n;

vector<vector<int> > es;

int read() {
  if (scanf("%d", &n) < 1) {
    return 0;
  }
  es = vector<vector<int> >(n);
  for (int i = 0; i < n - 1; ++i) {
    int s, t;
    scanf("%d%d", &s, &t);
    --s, --t;
    es[s].pb(t), es[t].pb(s);
  }
  return 1;
}

int dist[maxn];
int dist1[maxn];

void dfs1(int v, int p) {
  for (int u : es[v]) {
    if (u == p) {
      continue;
    }
    dist[u] = dist[v] + 1;
    dfs1(u, v);
  }
}

int used[maxn];

typedef vector<vector<int> > vvi;

int cnt[maxn];

void dfs2(int v, int p) {
  cnt[v] = 1;
  for (int u : es[v]) {
    if (u == p || used[u]) {
      continue;
    }
    dfs2(u, v);
    cnt[v] += cnt[u];
  }
}

int diam, D;

void adde(vvi &a) {
  int n = sz(a);
  for (int i = 0; i < n; ++i) {
    a[i].pb(0);
  }
  a.pb(vector<int>(n + 1, 0));

  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      int x = a[i][j];
      if (!x) {
        continue;
      }
      a[i][j] = 0;
      if (i + 1 <= D) {
        add(a[i + 1][j], x);
      }
      if (i + 1 <= D) {
        add(a[i][j + 1], x);
      }
    }
  }
}

void makesum(vvi &a) {
  for (int i = 0; i < sz(a); ++i) {
    for (int j = 0; j < sz(a); ++j) {
      int &res = a[i][j];
      if (i) {
        add(res, a[i - 1][j]);
        if (j) {
          add(res, mod - a[i - 1][j - 1]);
        }
      }
      if (j) {
        add(res, a[i][j - 1]);
      }
    }
  }
}

void makeone(vvi &a) {
  for (int i = sz(a) - 1; i >= 0; --i) {
    for (int j = sz(a) - 1; j >= 0; --j) {
      int &res = a[i][j];
      if (i) {
        add(res, mod - a[i - 1][j]);
        if (j) {
          add(res, a[i - 1][j - 1]);
        }
      }
      if (j) {
        add(res, mod - a[i][j - 1]);
      }
    }
  }
}

void update(vvi &a, vvi &b) {
  /*eprintf("update:\n");
  eprintf("%d\n", sz(a));
  for (int i = 0; i < sz(a); ++i) {
    for (int j = 0; j < sz(a); ++j) {
      eprintf("%d%c", a[i][j], " \n"[j == sz(a) - 1]);
    }
  }
  eprintf("%d\n", sz(b));
  for (int i = 0; i < sz(b); ++i) {
    for (int j = 0; j < sz(b); ++j) {
      eprintf("%d%c", b[i][j], " \n"[j == sz(b) - 1]);
    }
  }*/
  assert(sz(a) >= sz(b));

  makesum(a);
  makesum(b);
  for (int i = 0; i < sz(a); ++i) {
    for (int j = 0; j < sz(a); ++j) {
      a[i][j] = mult(a[i][j], b[min(sz(b) - 1, i)][min(sz(b) - 1, j)]);
    }
  }
  makeone(a);
}

vvi* dfs3(int v, int p) {
  int u0 = -1;
  for (int u : es[v]) {
    if (u == p || used[u]) {
      continue;
    }
    if (u0 == -1 || cnt[u] > cnt[u0]) {
      u0 = u;
    }
  }
  if (u0 == -1) {
    return new vvi({{1}});
  }
  auto ans = dfs3(u0, v);
  adde(*ans);

  for (int u : es[v]) {
    if (u == p || u == u0 || used[u]) {
      continue;
    }
    auto got = dfs3(u, v);
    adde(*got);
    if (sz(*ans) < sz(*got)) {
      swap(ans, got);
    }
    update(*ans, *got);
  }
  return ans;
}

int ans[maxn];
int adds[maxn];

void solve() {
  dist[0] = 0;
  dfs1(0, -1);
  int v = max_element(dist, dist + n) - dist;

  dist[v] = 0;
  dfs1(v, -1);
  int u = max_element(dist, dist + n) - dist;
  diam = dist[u];


  memcpy(dist1, dist, sizeof(dist[0]) * n);

  dist[u] = 0;
  dfs1(u, -1);

  D = (diam + 1) / 2;
  //eprintf("diam = %d\n", diam);

  for (int i = 0; i < n; ++i) {
    used[i] = 0;
  }
  int vs[2];
  int k = 0;
  for (int i = 0; i < n; ++i) {
    if (dist[i] + dist1[i] == diam && abs(dist[i] - dist1[i]) <= 1) {
      vs[k++] = i;
      used[i] = 1;
    }
  }
  assert(1 <= k && k <= 2);
  for (int i = 0; i < k; ++i) {
    dfs2(i, -1);
  }

  //eprintf("middle %d\n", vs[0]);

  int res = 0;
  if (k == 1) {
    dfs2(vs[0], -1);
    for (int i = 0; i <= D; ++i) {
      ans[i] = 1;
    }
    for (int u : es[vs[0]]) {
      auto &got = *dfs3(u, vs[0]);
      adde(got);
      for (int i = 0; i <= D; ++i) {
        adds[i] = 0;
      }
      for (int i = 0; i < sz(got); ++i) {
        for (int j = 0; j < sz(got); ++j) {
          int cur = got[i][j];
          if (!cur) {
            continue;
          }
          //eprintf("u = %d, (%d,%d) x%d\n", u, i, j, cur);
          int l = i, r = D - j;
          if (l <= r) {
            //eprintf("[%d..%d]\n", l, r);
            add(adds[l], cur);
            add(adds[r + 1], mod - cur);
          }
        }
      }
      int bal = 0;
      for (int i = 0; i <= D; ++i) {
        add(bal, adds[i]);
        ans[i] = mult(ans[i], bal);
      }
    }
    for (int i = 0; i <= D; ++i) {
      add(res, ans[i]);
    }
  } else {
    auto &ans1 = *(dfs3(vs[0], -1));
    auto &ans2 = *(dfs3(vs[1], -1));
    assert(sz(ans1) == D && sz(ans2) == sz(ans1));
    //eprintf("D = %d\n", D);
    for (int i = 0; i < sz(ans1); ++i) {
      add(res, mult(2, mult(ans1[i][D - 1 - i], ans2[i][D - 1 - i])));
      if (i) {
        add(res, mult(ans1[i][D - 1 - i], ans2[i][D - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i][D - i]));

        add(res, mult(ans1[i][D - 1 - i], ans2[i - 1][D - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i - 1][D - i]));
      }
      if (i < sz(ans1) - 1) {
        add(res, mult(ans1[i][D - 1 - i], ans2[i + 1][D - 1 - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i + 1][D - 1 - i]));
      }
    }
  }

  printf("%d\n", res);
  //exit(0);
}

int main() {
  precalc();
#ifdef LOCAL
  freopen(TASK ".out", "w", stdout);
  assert(freopen(TASK ".in", "r", stdin));
#endif

  while (1) {
    if (!read()) {
      break;
    }
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Submission Time
Task D - Oriented Tree
User XraY
Language C++14 (GCC 5.4.1)
Score 1800
Code Size 6753 Byte
Status AC
Exec Time 114 ms
Memory 3328 KB

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:71:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &s, &t);
                          ^

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 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 73 ms 3328 KB
1_02.txt AC 73 ms 3328 KB
1_03.txt AC 2 ms 512 KB
1_04.txt AC 2 ms 512 KB
1_05.txt AC 2 ms 384 KB
1_06.txt AC 2 ms 512 KB
1_07.txt AC 3 ms 512 KB
1_08.txt AC 3 ms 512 KB
1_09.txt AC 4 ms 512 KB
1_10.txt AC 7 ms 512 KB
1_11.txt AC 11 ms 512 KB
1_12.txt AC 28 ms 768 KB
1_13.txt AC 73 ms 1152 KB
1_14.txt AC 114 ms 1792 KB
1_15.txt AC 110 ms 2560 KB
1_16.txt AC 79 ms 3200 KB
1_17.txt AC 2 ms 512 KB
1_18.txt AC 2 ms 512 KB
1_19.txt AC 2 ms 512 KB
1_20.txt AC 2 ms 512 KB
1_21.txt AC 2 ms 512 KB
1_22.txt AC 2 ms 512 KB
1_23.txt AC 2 ms 512 KB
1_24.txt AC 2 ms 512 KB
1_25.txt AC 2 ms 512 KB
1_26.txt AC 2 ms 512 KB
1_27.txt AC 2 ms 512 KB
1_28.txt AC 2 ms 512 KB