Submission #658634

#	Time	Username	Problem	Language	Result	Execution time	Memory
658634		lunchbox1	Star Trek (CEOI20_startrek)	C++17	100 / 100	200 ms	23304 KiB

startrek

/*
 Star Trek
 https://oj.uz/problem/view/CEOI20_startrek
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5, P = 1e9 + 7;

struct dat {
 int a, b, c;
 bool g;

 dat(bool d) {
  a = b = c = -1, g = d;
 }
 void add(int i) {
  if (a == -1)
   a = i;
  else if (b == -1)
   b = i;
  else if (c == -1)
   c = i;
 }
 bool good(int i) {
  return (a != -1 && a != i) || (b != -1 && b != i) || (c != -1 && c != i) || g;
 }
};

struct mat {
 array<array<int, 2>, 2> v;
 
 mat(bool i = 0) {
  v[0][0] = v[0][1] = v[1][0] = v[1][1] = 0;
  if (i)
   v[0][0] = v[1][1] = 1;
 }
 mat operator*(mat o) {
  mat r;
  for (int a = 0; a < 2; a++)
   for (int b = 0; b < 2; b++)
    r.v[a][b] = (1LL * v[a][0] * o.v[0][b] + 1LL * v[a][1] * o.v[1][b]) % P;
  return r;
 }
};

vector<int> g[N];
array<int, 2> c[N];
bool w0[N], w1[N];

void dfs1(int i) {
 for (int j : g[i]) {
  g[j].erase(find(g[j].begin(), g[j].end(), i));
  dfs1(j), w0[i] |= !w0[j];
 }
}

void dfs2(int i, bool u) {
 w1[i] = !u;
 dat t(!u);
 for (int j : g[i])
  if (!w0[j])
   w1[i] = 1, t.add(j);
 for (int j : g[i])
  dfs2(j, t.good(j));
}

bool tmp;

void dfs3(int i) {
 dat t(0);
 for (int j : g[i])
  if (!w0[j])
   t.add(j);
 c[i][0] = c[i][1] = 0;
 for (int j : g[i]) {
  dfs3(j);
  (c[i][t.good(j) | !0] += c[j][0]) %= P;
  (c[i][t.good(j) | !1] += c[j][1]) %= P;
 }
 if (!tmp)
  c[i][w0[i] | !0]++;
 else
  c[i][w0[i] | !1]++;
}

mat m;

void dfs4(int i, bool u, array<int, 2> d) {
 dat t(0);
 if (!u)
  t.add(i);
 for (int j : g[i])
  if (!w0[j])
   t.add(j);
 int s0 = 0, s1 = 0;
 array<int, 2> q = {0, 0};
 q[t.good(i) || !0] += d[0], s0 += d[0];
 q[t.good(i) || !1] += d[1], s1 += d[1];
 for (int j : g[i]) {
  q[t.good(j) || !0] += c[j][0], s0 += c[j][0];
  q[t.good(j) || !1] += c[j][1], s1 += c[j][1];
 }
 swap(d, c[i]);
 for (int j : g[i]) {
  s0 -= c[j][0], s1 -= c[j][1];
  array<int, 2> e = {0, 0};
  e[t.good(j) | !tmp]++;
  e[1] += s0;
  if (t.c != -1)
   e[1] += s1;
  else if (t.b != -1) {
   if (j != t.a && j != t.b)
    e[1] += s1;
   else
    e[1] += s1 - c[t.a ^ t.b ^ j][1], e[0] += c[t.a ^ t.b ^ j][1];
  } else if (t.a != -1) {
   if (t.a == j)
    e[0] += s1;
   else
    e[1] += s1 - c[t.a][1], e[0] += c[t.a][1];
  } else
   e[0] += s1;
  dfs4(j, t.good(j), e);
  s0 += c[j][0], s1 += c[j][1];
 }
 swap(d, c[i]);
 q[t.good(-1) | !tmp]++;
 m.v[tmp][0] = (m.v[tmp][0] + q[0]) % P, m.v[tmp][1] = (m.v[tmp][1] + q[1]) % P;
}

int x, y;

array<int, 2> dfs5(int i) {
 dat t(0);
 for (int j : g[i])
  if (!w0[j])
   t.add(j);
 array<int, 2> c = {0, 0};
 for (int j : g[i]) {
  auto [c0, c1] = dfs5(j);
  (c[t.good(j) || !0] += c0) %= P;
  (c[t.good(j) || !1] += c1) %= P;
 }
 (c[w0[i] | !0] += x) %= P;
 (c[w0[i] | !1] += y) %= P;
 return c;
}

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n;
 long long k;
 cin >> n >> k;
 for (int h = 0; h < n - 1; h++) {
  int i, j;
  cin >> i >> j, i--, j--;
  g[i].push_back(j), g[j].push_back(i);
 }
 dfs1(0);
 dfs2(0, 1);
 tmp = 0;
 dfs3(0);
 dfs4(0, 1, {0, 0});
 tmp = 1;
 dfs3(0);
 dfs4(0, 1, {0, 0});
 mat p(1);
 k--;
 while (k > 0) {
  if (k & 1)
   p = p * m;
  m = m * m, k >>= 1;
 }
 int c = 0;
 for (int i = 0; i < n; i++)
  c += w1[i];
 x = (1LL * (n - c) * p.v[0][0] + 1LL * c * p.v[1][0]) % P;
 y = (1LL * (n - c) * p.v[0][1] + 1LL * c * p.v[1][1]) % P;
 cout << dfs5(0)[1] << '\n';
 return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15