01/11
14:21
OI

[Jsoi2010]游戏 [树形DP]

[Jsoi2010]游戏

考场rush 50分,挂成10分了5555

给一个数列,判断是否合法。

注意到只需要二进制后3位,5^k\mod 8意义下,1 \rightarrow 5 \rightarrow 1 \rightarrow 5 …。注意到15的后两位都是01,说明后两位只与和有关,只需关注第三位。

第三位除了被和影响,还会被乘5^{2k}的数的第一位影响。如果所有数都是01,显然没有选择,否则可以自由组成想要的01,这是因为对任意方案取反即可得到另一种。

一种方案可以看作一个边上有颜色的三角,ans = \binom{n}{3} – uu是不合法方案数量。不合法方案等于三边颜色不全相同的三角。可以枚举两条颜色不同的边计算。

定义f_{x,i,j,k}, i < 8, j < 4, k < 3x点,选的数列\mod 8 = i,数列的第一位和\mod 4 = j,这个数列为全0,全1,或都有。求出根的方案树,进而换根求出总方案数。

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 2e5 + 233;

int n, val1[N], val2[N], root;
long long f[N][8][4][3], ans;
std::vector<int> G[N];

inline void update(int x, int y, int v) {
  for (int i = 0; i < 8; ++i) {
    int s = (val1[x] + i) & 7;
    for (int j = 0; j < 4; ++j) {
      int t = (val2[x] + j) & 3;
      for (int k = 0; k < 3; ++k)
        f[x][s][t][(k == 1) != val2[x] ? 2 : k] += f[y][i][j][k] * v;
    }
  }
}

void dfs1(int x) {
  for (int y : G[x]) {
    dfs1(y);
    update(x, y, 1);
  }
  ++f[x][val1[x]][val2[x]][val2[x]];
}

inline void get_ans(int x) {
  --f[x][val1[x]][val2[x]][val2[x]];
  long long tmp = 0;
  for (int j = 0; j < 4; ++j) {
    tmp += f[x][3][j][0] + f[x][3][j][2] + f[x][7][j][2];
    if (j & 2)
      tmp += f[x][7][j][1];
    else
      tmp += f[x][3][j][1];
  }
  ans += tmp * (n - tmp - 1);
  ++f[x][val1[x]][val2[x]][val2[x]];
}

void dfs2(int x) {
  get_ans(x);
  for (int y : G[x]) {
    update(x, y, -1);
    update(y, x, 1);
    dfs2(y);
    update(y, x, -1);
    update(x, y, 1);
  }
}

int main() {
  n = rd();
  for (int i = 1; i <= n; ++i) {
    int fa = rd(), v = rd();
    val1[i] = v & 7;
    val2[i] = v & 1;
    if (!fa) root = i;
    else G[fa].push_back(i);
  }
  dfs1(root), dfs2(root);
  ans = 1ll * n * (n - 1) * (n - 2) / 6 - ans / 2;
  std::cout << ans << std::endl;
  return 0;
}