比赛链接

C-A National Pandemic

我们考虑将操作1全部转换为对根的操作。

考虑转化之后带来的影响:

  1. 对于u的子树中的点,权值需要加(dep[u] - 1) * 2
  2. 对于u到根的链上,需要加一个等差数列。
  3. 对于其他的点,需要先找到和u的lca,这个点必定在u到根的链上。在查询的时候我们需要加上这个点的偏移值。我们可以通过维护差分序列实现。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define lson (rt << 1)
#define rson (lson | 1)
const int maxn = 5e4 + 5;
vector<int> G[maxn];
int a[maxn];

int sum[maxn << 2], lazy[maxn << 2];

void pushdown(int rt, int llen, int rlen) {
  sum[lson] += lazy[rt] * llen;
  sum[rson] += lazy[rt] * rlen;
  lazy[lson] += lazy[rt];
  lazy[rson] += lazy[rt];
  lazy[rt] = 0;
}
void add(int l, int r, int rt, int L, int R, int x) {
  if (L <= l && R >= r) {
    sum[rt] += (r - l + 1) * x;
    lazy[rt] += x;
    return;
  }
  int m = l + r >> 1;
  pushdown(rt, m - l + 1, r - m);
  if (L <= m) add(l, m, lson, L, R, x);
  if (m + 1 <= R) add(m + 1, r, rson, L, R, x);
  sum[rt] = sum[lson] + sum[rson];
}
int query(int l, int r, int rt, int L, int R) {
  if (L <= l && R >= r) return sum[rt];
  int m = l + r >> 1;
  pushdown(rt, m - l + 1, r - m);
  int ret = 0;
  if (L <= m) ret += query(l, m, lson, L, R);
  if (m + 1 <= R) ret += query(m + 1, r, rson, L, R);
  return ret;
}

struct HLD {
  int n, dfn;
  int sz[maxn], top[maxn], son[maxn], dep[maxn], par[maxn], id[maxn], rk[maxn];
  void init(int n) {
    this->n = n;
    dfn = 0;
    for (int i = 0; i <= n; i++) son[i] = -1;
    for (int i = 0; i <= n; i++) G[i].clear();
  }
  void build() {
    dfs(1, 1, 1);
    link(1, 1);
  }
  void dfs(int u, int fa, int d) {
    dep[u] = d;
    par[u] = fa;
    sz[u] = 1;
    for (auto &v : G[u]) {
      if (v == fa) continue;
      dfs(v, u, d + 1);
      sz[u] += sz[v];
      if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
    }
  }
  void link(int u, int t) {
    top[u] = t;
    id[u] = ++dfn;
    rk[dfn] = u;
    if (son[u] == -1) return;
    link(son[u], t);  // 保证重链的dfs序是连续的
    for (auto &v : G[u]) {
      if (v != son[u] && v != par[u]) link(v, v);
    }
  }

  void update_path(int u, int v, int w) {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      add(1, n, 1, id[top[u]], id[u], w);
      u = par[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    add(1, n, 1, id[u], id[v], w);  // 点权
  }
  int query_path(int u, int v) {
    int ret = 0;
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) swap(u, v);
      ret += query(1, n, 1, id[top[u]], id[u]);
      u = par[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ret += query(1, n, 1, id[u], id[v]);  // 点权
    return ret;
  }
} hld;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(sum, 0, sizeof(sum));
    memset(lazy, 0, sizeof(lazy));
    memset(a, 0, sizeof(a));
    hld.init(n);
    for (int i = 0, u, v; i < n - 1; i++) {
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    hld.build();

    int foo = 0, bar = 0;
    for (int i = 0, op, x, w; i < m; i++) {
      scanf("%d", &op);
      if (op == 1) {
        scanf("%d%d", &x, &w);
        hld.update_path(1, x, 2);
        foo += w + 1 - hld.dep[x], bar += 1;
      } else if (op == 2) {
        scanf("%d", &x);
        int tmp = hld.query_path(1, x) + foo - bar * (hld.dep[x] + 1);
        if (a[x] + tmp > 0) a[x] = -tmp;
      } else {
        scanf("%d", &x);
        int tmp = hld.query_path(1, x) + foo - bar * (hld.dep[x] + 1);
        printf("%d\n", tmp + a[x]);
      }
    }
  }
}

I-Valuable Forests

根据prufer序列的性质可知有标号无根树的数量为:

$a(n) = n^{n-2}$

那么有标号无根树森林的数量可以通过dp推出:

$b(n) = \sum_{i=0}^{n-1}\binom{n-1}{i} \ a(i+1) \ b(n-1-i)$

枚举第i个点所在的树的大小。

接着可以算出$n$个点的无根树的答案:

$c(n) = n \sum_{i=1}^{n-1} \binom{n-2}{i-1} \ i^2 \ (n-1)^{n-1-i}$

选一个点枚举度数。由prufer序列性质可知,一个点的度数为$d$,说明其在序列中出现了$d-1$次。枚举完度数后,需要计算有多少个序列中出现了$d-1$次该点。

最后答案为:

$f(n) = \sum_{i=1}^{n} \binom{n-1}{i-1} ( c(i) b(n-i) + a(i) f(n-i))$

枚举第n个点所在的树的大小。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5001;
int Pow(int a, int b, int mod) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = (ll)a * ret % mod;
    a = (ll)a * a % mod;
    b >>= 1;
  }
  return ret;
}
int a[maxn], b[maxn], c[maxn], f[maxn], cb[maxn][maxn];

int main() {
  int T, mod, n;
  scanf("%d%d", &T, &mod);
  cb[0][0] = 1;
  for (int i = 1; i < maxn; i++) {
    cb[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      cb[i][j] = (cb[i - 1][j] + cb[i - 1][j - 1]) % mod;
    }
  }
  a[1] = 1, b[0] = 1;
  for (int i = 2; i < maxn; i++) a[i] = Pow(i, i - 2, mod);
  for (int i = 1; i < maxn; i++) {
    for (int j = 0; j < i; j++) {
      b[i] += (ll)cb[i - 1][j] * a[j + 1] % mod * b[i - 1 - j] % mod;
      b[i] %= mod;
    }
  }
  cerr << b[1] << endl;
  for (int i = 2; i < maxn; i++) {
    for (int j = 1; j < i; j++) {
      c[i] += (ll)cb[i - 2][j - 1] * j % mod * j % mod *
              Pow(i - 1, i - 1 - j, mod) % mod;
      c[i] %= mod;
    }
    c[i] = (ll)c[i] * i % mod;
  }
  for (int i = 1; i < maxn; i++) {
    for (int j = 1; j <= i; j++) {
      int tmp = ((ll)c[j] * b[i - j] % mod + (ll)a[j] * f[i - j] % mod) % mod;
      f[i] += (ll)cb[i - 1][j - 1] * tmp % mod;
      f[i] %= mod;
    }
  }
  while (T--) {
    scanf("%d", &n);
    printf("%d\n", f[n]);
  }
}
最后修改:2020 年 08 月 03 日 11 : 27 AM