Tag: Centroid Decomposition

题目描述

ZS the Coder has a large tree. It can be represented as an undirected connected graph of $n$ vertices numbered from $0$ to $n-1$ and $n-1$ edges between them. There is a single nonzero digit written on each edge.
One day, ZS the Coder was bored and decided to investigate some properties of the tree. He chose a positive integer $M$, which is coprime to $10$, i.e. $(M, 10)=1$.
ZS consider an ordered pair of distinct vertices $(u, v)$ interesting when if he would follow the shortest path from vertex $u$ to vertex $v$ and write down all the digits he encounters on his path in the same order, he will get a decimal representaion of an integer divisible by $M$.
Formally, ZS consider an ordered pair of distinct vertices $(u, v)$ interesting if the following states true:

• let $a_1=u, a_2, \ldots, a_k=v$ be the sequence of vertices on the shortest path from $u$ to $v$ in the order of encountering them;
• let $d_i (1 \le i \lt k)$ be the digit written on the edge between vertices $a_i$ and $a_i+1$;
• the integer $\overline{d_1d_2 \ldots d_{k-1}}=\sum_{i=1}^{k-1} 10^{k-1-i}d_i$ is divisible by $M$.

Help ZS the Coder find the number of interesting pairs!

题意概述

给定一棵有$n$个节点的树和一个与$10$互质的数$M$，树上每条边的权值都是小于$10$的正整数。定义$dist_{u, v}$为依次写下从$u$到$v$路径上每条边的权值所得到的数字。求满足$M \mid dist_{u, v}$的点对个数。
数据范围：$2 \le n \le 10^5, \; 1 \le M \le 10^9$。

算法分析

设当前枚举到的节点为$x$。令$depth_u$表示$u$在$x$及它子树中的深度。对于在$x$第$(i+1)$棵子树中的节点$u$和在前$i$棵子树中的节点$v$，有：
$$
\begin{align}
M \mid dist_{u, v} \Leftrightarrow 10^{depth_v}dist_{u, x}+dist_{x, v} \equiv 0 \pmod M \tag{1} \\
M \mid dist_{v, u} \Leftrightarrow 10^{depth_u}dist_{v, x}+dist_{x, u} \equiv 0 \pmod M \tag{2}
\end{align}
$$
对于$(1)$式，化简得$dist_{u, x} \equiv -10^{-depth_v}dist_{x, v} \pmod M$；对于$(2)$式，化简得$10^{-depth_u}dist_{x, u} \equiv -dist_{v, x} \pmod M$。用两个map分别存下前$i$棵子树中$10^{-depth_v}dist_{x, v}$和$dist_{v, x}$的值，在处理第$(i+1)$棵子树时直接加上可行的方案数。

代码

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
struct edge {
    int v, w, nxt;
} e[200001];
long long n, m, ans, nume, tot, root, h[100001], size[100001], f[100001];
long long val1[100001], val2[100001], power[100001], inv[100001];
bool vis[100001];
map<long long, int> id1, id2;
void extend_gcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return; }
    extend_gcd(b, a % b, y, x);
    y -= a / b * x;
}
void add_edge(int u, int v, int w) {
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag, int depth) {
    if (!flag) ++id1[val1[t]], ++id2[val2[t] * inv[depth] % m];
    else {
        ans += !val1[t] + !val2[t];
        ans += id1[(val2[t] ? m - val2[t] : 0) * inv[depth] % m];
        ans += id2[val1[t] ? m - val1[t] : 0];
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            if (flag) {
                val1[e[i].v] = (val1[t] + e[i].w * power[depth]) % m;
                val2[e[i].v] = (val2[t] * 10 + e[i].w) % m;
            }
            get_dist(e[i].v, t, flag, depth + 1);
        }
    }
}
void solve(int t) {
    vis[t] = true, id1.clear(), id2.clear();
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val1[e[i].v] = val2[e[i].v] = e[i].w % m;
            get_dist(e[i].v, t, 1, 1);
            get_dist(e[i].v, t, 0, 1);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = n, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    scanf("%lld%lld", &n, &m);
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * 10 % m;
    for (int i = 0; i <= n; ++i) {
        int x, y;
        extend_gcd(power[i], m, x, y);
        inv[i] = (x % m + m) % m;
    }
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
    }
    tot = f[n] = n, root = n;
    get_root(0, n);
    solve(root);
    printf("%lld\n", ans);
    return 0;
}

题目描述

There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with $N$ vertices, while each branch can be treated as a vertex). Today the students under the tree are considering a problem: Can we find such a chain on the tree so that the multiplication of all integers on the chain (mod $10^6 + 3$) equals to $K$?
Can you help them in solving this problem?

题意概述

给定一棵有$N$个节点的树，其中第$i$个节点的权值为$v_i$。求一个字典序最小的点对使得这两点之间路径上的点权之积模$10^6+3$等于$K$。
数据范围：$1 \le N \le 10^5, \; 0 \le K \lt 10^6+3, \; 1 \le v_i \lt 10^6+3$。

算法分析

点分治。设当前枚举到的节点为$x$，其第$i$棵子树的根节点为$x_i$。用map储存下$x$前$i$棵子树中的节点到$x$儿子的可能的乘积。在计算第$(i+1)$棵子树时，设当前计算的节点到$x_{i+1}$的乘积为$p$，若map中存在$q$满足$p \times q \times x \equiv K \pmod {10^6+3}$，即$q \equiv K \times p^{-1} \times x^{-1} \pmod {10^6+3}$，则将这两个节点与当前答案比较，取较优解。

代码

#include <cstdio>
#include <map>
#include <algorithm>
#include <cstring>
#define MOD 1000003
using namespace std;
struct edge {
    int v, nxt;
} e[200001];
long long n, k, x, y, root, nume, tot, inv[MOD], h[100001], v[100001], size[100001], f[100001], val[100001];
bool vis[100001];
map<long long, int> id;
void add_edge(int u, int v) {
    e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
    e[++nume].v = u, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
    size[t] = 1, f[t] = 0;
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            get_root(e[i].v, t);
            size[t] += size[e[i].v];
            f[t] = max(f[t], size[e[i].v]);
        }
    }
    f[t] = max(f[t], tot - size[t]);
    if (f[t] < f[root]) root = t;
}
void update(int a, int b) {
    if (a > b) swap(a, b);
    if (a < x) x = a, y = b;
    else if (a == x && b < y) y = b;
}
void get_dist(int t, int fa, int flag) {
    if (!flag) {
        if (!id.count(val[t])) id[val[t]] = t;
        else id[val[t]] = min(id[val[t]], t);
    } else {
        if (val[t] * val[root] % MOD == k) {
            if (t <= x || root <= x) update(t, root);
        }
        long long inverse = k * inv[val[t]] % MOD * inv[val[root]] % MOD;
        if (id.count(inverse)) {
            if (id[inverse] <= x || t <= x) update(id[inverse], t);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v] && e[i].v != fa) {
            if (flag) val[e[i].v] = val[t] * v[e[i].v] % MOD;
            get_dist(e[i].v, t, flag);
        }
    }
}
void solve(int t) {
    vis[t] = true, val[t] = v[t], id.clear();
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            val[e[i].v] = v[e[i].v];
            get_dist(e[i].v, t, 1);
            get_dist(e[i].v, t, 0);
        }
    }
    for (int i = h[t]; i; i = e[i].nxt) {
        if (!vis[e[i].v]) {
            root = 0, tot = size[e[i].v];
            get_root(e[i].v, t);
            solve(root);
        }
    }
}
int main()
{
    inv[1] = 1;
    for (int i = 2; i < MOD; ++i) {
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    while (scanf("%lld%lld", &n, &k) != -1) {
        x = y = 1e9, nume = 0;
        memset(vis, 0, sizeof(vis));
        memset(h, 0, sizeof(h));
        for (int i = 1; i <= n; ++i) scanf("%lld", &v[i]);
        for (int i = 1; i < n; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
        }
        tot = f[0] = n, root = 0;
        get_root(1, 0);
        solve(root);
        if (y <= n) printf("%lld %lld\n", x, y);
        else printf("No solution\n");
    }
    return 0;
}