头像

垫底抽风




离线:4天前


最近来访(13434)
用户头像
bre
用户头像
DreamFather
用户头像
旺旺小仙贝
用户头像
桑塔露琪亚
用户头像
AFL
用户头像
L-China
用户头像
罚时大师月色
用户头像
acwing_49062
用户头像
写不出来没有bug的bug
用户头像
学到世界末日那天
用户头像
acwing_6339
用户头像
Stair
用户头像
筱_5
用户头像
卷卷死他们
用户头像
77777777777
用户头像
模拟题都不会
用户头像
蓝色骨头
用户头像
SugarLife
用户头像
废物宝宝
用户头像
yeyushengfan

新鲜事 原文

垫底抽风
6个月前
摸了一个端午,怎么办?


新鲜事 原文

垫底抽风
6个月前
找不到思路怎么办???


新鲜事 原文

垫底抽风
6个月前
???


新鲜事 原文

垫底抽风
6个月前
怎么解释一些很难解释的事情?



垫底抽风
6个月前

题目描述

给定一棵 $n$ 个节点的树。每条边有一种颜色。

记 $f(u, v)$ 表示从 $u$ 到 $v$ 的路径上,出现且只出现一次的颜色的数量。

求 $\displaystyle \sum _ {u = 2} ^ n \sum _ {v = 1} ^ {u - 1} f(u, v)$。

输入格式

第一行包含一个正整数,表示 $n$。

接下来 $n - 1$ 行,每行包含三个整数 $u, v, c$,表示一条连接 $u, v$,颜色是 $c$ 的边。

保证输入构成一棵树。

输出格式

一行一个整数,表示答案。

数据范围

$2 \leq n \leq 5 \times 10 ^ 5$。

$1 \leq u, v, c \leq n$。

输入样例 1

3
1 2 1
1 3 2

输出样例 1

4

输入样例 2

3
1 2 2
1 3 2

输出样例 2

2

输入样例 3

5
1 4 4
1 2 3
3 4 4
4 5 5

输出样例 3

14

输入样例 4

2
2 1 1

输出样例 4

1

输入样例 5

10
10 2 3
3 8 8
4 8 9
5 8 5
3 10 7
7 8 2
5 6 6
9 3 4
1 6 3

输出样例 5

120

算法 1

(动态树,LCT) $O(n \log n)$

对每个颜色算贡献。可以得到如下算法。

枚举每个颜色 $c$,将所有颜色不为 $c$ 的边建出来。此时树被划分为若干连通块。

对于每条颜色为 $c$ 的边 $(u, v)$,当一条路径一端在 $u$ 所在连通块内,另一端在 $v$ 所在连通块内时,该边对该路径有贡献。记节点 $x$ 所在连通块大小为 $s _ x$,则该边贡献为 $s _ u \times s _ v$。

使用并查集维护连通块及其大小,每次暴力加边,这样复杂度是 $O(n ^ 2 \alpha (n))$。

考虑优化。

上述过程可以用动态树维护。初始时将所有边加进去。对于每个颜色 $c$,将所有颜色为 $c$ 的边断开,计算该颜色贡献,再将断开的边重新连上。

时间复杂度

每条边被加、删常数次,时间复杂度为 $O(n \log n)$。

C++ 代码

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

#define eb emplace_back

using namespace std;

typedef long long LL;
const int N = 500005;

int n;
struct Tree {
    int p, s[2], v, sv;
    bool rev;
} tr[N];
int stk[N];

#define L tr[z].s[0]
#define R tr[z].s[1]

void update(int z) {
    tr[z].sv = tr[L].sv + tr[R].sv + tr[z].v;
}

void pushrev(int z) {
    swap(L, R);
    tr[z].rev ^= 1;
}

void pushdown(int z) {
    if (tr[z].rev) {
        pushrev(L);
        pushrev(R);
        tr[z].rev = false;
    }
}

bool isroot(int z) {
    return tr[tr[z].p].s[0] != z && tr[tr[z].p].s[1] != z;
}

void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    bool k = tr[y].s[1] != x;
    if (!isroot(y)) tr[z].s[tr[z].s[1] == y] = x;
    tr[x].p = z;
    tr[y].s[!k] = tr[x].s[k], tr[tr[x].s[k]].p = y;
    tr[x].s[k] = y, tr[y].p = x;
    update(y), update(x);
}

void splay(int x) {
    int r = x, tt = 0; stk[++tt] = r;
    while (!isroot(r)) stk[++tt] = r = tr[r].p;
    while (tt) pushdown(stk[tt--]);
    while (!isroot(x)) {
        int y = tr[x].p, z = tr[y].p;
        if (!isroot(y)) {
            if ((tr[z].s[1] == y) != (tr[y].s[1] == x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}

void access(int z) {
    int r = z;
    for (int y = 0; z; y = z, z = tr[z].p) {
        splay(z);
        tr[z].v -= tr[y].sv;
        tr[z].v += tr[R].sv;
        tr[z].s[1] = y;
        update(z);
    }
    splay(r);
}

void makeroot(int z) {
    access(z);
    pushrev(z);
}

int findroot(int z) {
    access(z);
    while (L) {
        pushdown(z);
        z = L;
    }
    splay(z);
    return z;
}

void split(int x, int y) {
    makeroot(x);
    access(y);
}

#undef L
#undef R

void edge(int x, int y) {
    makeroot(x);
    if (findroot(y) != x) {
        tr[x].p = y;
        access(y);
        tr[y].v += tr[x].sv;
        for (int z = y; z; z = tr[z].p) {
                tr[z].sv += tr[x].sv;
        }
    } else while (true);
}

void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && tr[y].p == x && !tr[y].s[0]) {
        tr[x].sv -= tr[y].sv;
        tr[x].s[1] = tr[y].p = 0;
    } else while (true);
}

LL res;
struct Edge {int x, y;};
vector<Edge> e[N];

int main() {
    scanf("%d", &n);
    for (int x = 1; x <= n; ++x) {
        tr[x].v = tr[x].sv = 1;
    }
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        edge(x, y);
        e[c].eb((Edge){x, y});
    }
    for (int c = 1; c <= n; ++c) {
        if (e[c].empty()) continue;
        for (auto [x, y] : e[c]) {
            cut(x, y);
        }
        for (auto [x, y] : e[c]) {
            makeroot(x), makeroot(y);
            res += tr[x].sv * (LL)tr[y].sv;
        }
        for (auto [x, y] : e[c]) {
            edge(x, y);
        }
    }
    printf("%lld\n", res);
    return 0;
}

算法 2

(虚树) $O(n \log n)$

要算贡献,本质是要算对于每个颜色,将所有该颜色边删了后,每个连通块的大小。

设 $1$ 号节点为根,每个点的深度为 $1$ 到该点的距离。

现在计算颜色为 $c$ 的边的贡献。记颜色为 $c$ 的边为虚边,其它边为实边。

欲快速计算每个实边连通块大小。

对于每个连通块,考虑其中深度最小的节点 $u$,可以发现整个连通块恰是 $u$ 的子树一部分。

更具体地考虑,哪些点会在该连通块内?哪些点不在?

若 $u$ 的子树中的一个点 $v$ 到 $u$ 的路径上,存在一条虚边,则 $v$ 与 $u$ 在一个连通块内。

这看似是句废话,实则启发我们,每个连通块大小,可以通过一个点 $u$ 的子树大小,减去若干 $u$ 的子树中节点 $v$ 的子树大小得到。

更具体一些,可以按照如下方式计算:

  • 对于每个点 $u$,处理出其子树大小 $sz[u]$。

  • 对于每条虚边 $(v, u) \ (dep[v] < dep[u])$:

    • 令 $w = sz[u]$。
    • 枚举 $u$ 的子树中一条虚边 $(x, y) (dep[x] < dep[y])$,若 $x$ 到 $u$ 的路径上不存在另一条虚边,则令 $w$ 减去 $sz[y]$。
    • 此时 $w$ 即为 $u$ 所在连通块大小。

发现上述过程只与每条虚边向下连接的点有关。将这些点拿出来建虚树即可。

因为只求连通块大小,实现时不需要将虚树中额外(若干点的 $\text{LCA}$)节点建出来。

时间复杂度

每个点恰好在一次建虚树过程中用到。总复杂度为 $O(n \log n)$。

C++ 代码

#include <stdio.h>
#include <string.h>

#include <vector>
#include <algorithm>

#define eb emplace_back

using namespace std;

typedef long long LL;
const int N = 500005, M = 1000005;

int n, dfn[N], f[N], ids;
int h[N], e[M], ne[M], w[M], idx;
int top[N], dep[N], son[N], sz[N], fa[N];
int stk[N], tt;
vector<int> v[N];

void add(int x, int y, int c) {
    e[++idx] = y, w[idx] = c, ne[idx] = h[x], h[x] = idx;
}

bool cmp(int x, int y) {
    return dfn[x] < dfn[y];
}

void dfs1(int x) {
    sz[x] = 1, dfn[x] = ++ids;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fa[x]) continue;
        v[w[i]].eb(y);
        fa[y] = x, dep[y] = dep[x] + 1, dfs1(y), sz[x] += sz[y];
        if (sz[y] > sz[son[x]]) son[x] = y;
    }
}

void dfs2(int x, int t) {
    top[x] = t;
    if (son[x]) {
        dfs2(son[x], t);
        for (int i = h[x]; i; i = ne[i]) {
            int y = e[i];
            if (y != son[x] && y != fa[x]) dfs2(y, y);
        }
    }
}

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) {
            y = fa[top[y]];
        } else {
            x = fa[top[x]];
        }
    }
    return dep[x] < dep[y] ? x : y;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c), add(y, x, c);
    }
    LL res = 0;
    dfs1(1), dfs2(1, 1);
    for (int c = 1; c <= n; ++c) if (v[c].size()) {
        sort(v[c].begin(), v[c].end(), cmp);
        tt = 0;
        int ids = 0;
        for (int u : v[c]) {
            w[u] = sz[u], f[u] = 0;
            int z = lca(u, stk[tt]);
            while (dep[stk[tt]] > dep[z]) {
                int x = stk[tt--], y = stk[tt];
                w[y] -= sz[x];
                f[x] = y;
            }
            stk[++tt] = u;
        }
        while (tt > 1) {
            int x = stk[tt--], y = stk[tt];
            w[y] -= sz[x];
            f[x] = y;
        }
        w[0] = n;
        for (int u : v[c]) {
            if (!f[u]) w[0] -= sz[u];
        }
        for (int u : v[c]) {
            res += w[u] * (LL)w[f[u]];
        }
    }
    printf("%lld\n", res);
    return 0;
}

算法 3

(分治,并查集) $O(n \log n)$

试图拓展算法 1 中复杂度为 $O(n ^ 2 \alpha(n))$ 的暴力并查集算法。

该算法的时间复杂度瓶颈在于,对于每种颜色,需要将并查集清空,重新连边。而很多边在之后的颜色中,需要重新连上。这些计算是冗余的。

具体一些,如果某个时刻将颜色在 $k + 1 \sim n$ 中的所有边都连上,那么在计算 $1 \sim k$ 中的所有颜色贡献时,可以尝试维持这些边的保留状态,通过改变其它边,达到需要的状态。

考虑分治,设 $solve(l, r)$ 计算 $[l, r]$ 这段区间中颜色的贡献:

  • 若 $l \neq r$
    • 取 $\displaystyle mid = \frac {l + r} 2$。
    • 将颜色在 $[mid + 1, r]$ 的边连接上。计算 $[l, mid]$ 中颜色贡献时需要这些边。调用 $solve(l, mid)$。
    • 撤销上面所连接的边。
    • 将颜色在 $[l, mid]$ 的边连上。在计算 $[mid + 1, r]$ 中颜色贡献时需要这些边。调用 $solve(mid+ 1, r)$。
    • 撤销上面所连接的边。
  • 否则,此时已经将 $[1, r - 1]$ 和 $[r + 1, n]$ 这些边连上。那么枚举所有颜色为 $r$ 的边,计算贡献即可。

考虑上面分治中涉及什么操作:

  • 连边。
  • 撤销连边。
  • 查一个给定点所在连通块大小。

可以使用 $\text{LCT}$。但注意到上面的操作不是断开任意一条边,而是撤销上一次连边,这可以使用可撤销并查集维护。

具体地,维护一个并查集,不路径压缩。那么为了保证复杂度,就需要按秩合并。每次记录修改的两个节点。撤销时反向操作即可。

时间复杂度

每条边会被连接 $O(\log n)$ 次。每次连接复杂度为 $O(\log n)$。所以时间复杂度为 $O(n \log ^ 2 n)$。

实际运行效率优于 $\text{LCT}$

C++ 代码

#include <stdio.h>
#include <string.h>

#include <vector>

#define eb emplace_back

using namespace std;

typedef long long LL;
const int N = 500005;

int n;
LL res;
struct Edge {int x, y;};
vector<Edge> v[N];
Edge stk[N]; int tt;
int p[N], sz[N];

int find(int x) {
    return x != p[x] ? find(p[x]) : x;
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    p[y] = x, sz[x] += sz[y];
    stk[++tt] = (Edge){x, y};
}

void revoke() {
    int x = stk[tt].x, y = stk[tt].y;
    sz[x] -= sz[y], p[y] = y, --tt;
}

void solve(int l, int r) {
    if (l == r) {
        for (Edge &e : v[r]) {
            res += sz[find(e.x)] * (LL)sz[find(e.y)];
        }
        return;
    }
    int cur = tt;
    int mid = l + r >> 1;
    for (int k = r; k > mid; --k) {
        for (Edge &e : v[k]) {
            merge(e.x, e.y);
        }
    }
    solve(l, mid);
    while (tt > cur) {
        revoke();
    }
    for (int k = l; k <= mid; ++k) {
        for (Edge &e : v[k]) {
            merge(e.x, e.y);
        }
    }
    solve(mid + 1, r);
    while (tt > cur) {
        revoke();
    }
}

int main() {
    scanf("%d", &n);
    for (int x = 1; x <= n; ++x) {
        p[x] = x, sz[x] = 1;
    }
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        v[c].eb((Edge){x, y});
    }
    solve(1, n);
    printf("%lld\n", res);
    return 0;
}

算法 4

(点分治) $O(n \log ^ 2 n)$ 或 $O(n \log n)$

考虑点分治。对于每个分治部分,计算所有经过重心的路径贡献。

对每个颜色开桶,记录该颜色边的出现次数。该次数只有为 $0$、$1$ 时对答案有贡献。贡献是 $0$ 和 $1$ 的数量的成绩。

对整个部分算答案,会算入子树贡献,根据点分治经典套路,在处理各子树时减去即可。

时间复杂度

这里每层将颜色去重时是通过排序,时间复杂度为 $O(n \log ^ 2 n)$。

因为值域不大,可以用 bool 数组记录,时间复杂度为 $O(n \log n)$。

C++ 代码

#include <stdio.h>
#include <string.h>

#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 500005, M = 1000005;

int n;
LL res;
int h[N], e[M], ne[M], w[M], idx;

int sz[N], szA, rt, mv;
int f[N], g[N], szf, szg;
int cnt[N], bv[N], cv[N], bw[N], cw[N];
bool st[N];

void add(int x, int y, int c) {
    e[++idx] = y, w[idx] = c, ne[idx] = h[x], h[x] = idx;
}

void center(int x, int fat) {
    int t = 0;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fat || st[y]) continue;
        center(y, x);
        t = max(t, sz[y]);
    }
    t = max(t, szA - sz[x]);
    if (t < mv) mv = t, rt = x;
}

void getsz(int x, int fat) {
    sz[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fat || st[y]) continue;
        getsz(y, x), sz[x] += sz[y];
    }
}

void dfs(int x, int fat) {
    sz[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fat || st[y]) continue;
        ++cnt[w[i]];
        dfs(y, x), sz[x] += sz[y];
        if (cnt[w[i]] == 1) {
            cv[w[i]] -= sz[y];
            g[szg++] = w[i];
        } else if (cnt[w[i]] == 2) {
            cw[w[i]] -= sz[y];
        }
        --cnt[w[i]];
    }
}

void solve(int x) {
    getsz(x, 0), szA = sz[x], mv = N, center(x, 0), st[x = rt] = true;
    szf = 0;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (st[y]) continue;
        szg = 0;
        ++cnt[w[i]];
        dfs(y, x);
        int szy = sz[y];
        cv[w[i]] = -szy, g[szg++] = w[i];
        --cnt[w[i]];
        for (int k = 0; k < szg; ++k) {
            res -= (cv[g[k]] + szy) * (LL)(cw[g[k]] - cv[g[k]]);
            bv[g[k]] += cv[g[k]], bw[g[k]] += cw[g[k]];
            cv[g[k]] = cw[g[k]] = 0;
        }
        memcpy(f + szf, g, szg << 2);
        szf += szg;
    }
    sort(f, f + szf);
    szf = unique(f, f + szf) - f;
    for (int i = 0; i < szf; ++i) {
        res += (bv[f[i]] + szA) * (LL)(bw[f[i]] - bv[f[i]]);
        bv[f[i]] = bw[f[i]] = 0;
    }
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (st[y]) continue;
        solve(y);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c), add(y, x, c);
    }
    solve(1);
    printf("%lld\n", res);
    return 0;
}

算法 5

(dfs) $O(n)$

虚树的做法是将每种颜色分开处理。这里将所有颜色一起处理。

记 $u$ 的父亲为 $fa _ u$,计算 $(u, fa _ u)$ 这条边连接的两个连通块大小。

记 $c _ u$ 表示考虑 $(u, fa _ u)$ 这条边时,$u$ 所在连通块大小。

与虚树类似,初始时 $c _ u = sz _ u$,$dfs$ 时记录路径中每个颜色的深度最深的边。

每次遍历颜色为 $t$ 的边,找到上一条颜色为 $t$ 的边 $(fa _ u, u, t)$,更新 $c _ u$ 即可。

时间复杂度

一次 $dfs$ 算子树大小,一次 $dfs$ 算 $c$。时间复杂度为 $O(n)$。

C++ 代码

#include <stdio.h>
#include <string.h>

typedef long long LL;
const int N = 500005, M = 1000005;

int n;
LL res;
int h[N], e[M], ne[M], w[M], idx;
int fa[N], sz[N], c[M];
int pre[N], last[N];

void add(int x, int y, int c) {
    e[++idx] = y, w[idx] = c, ne[idx] = h[x], h[x] = idx;
}

void dfs1(int x) {
    sz[x] = 1;
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fa[x]) continue;
        fa[y] = x, dfs1(y), sz[x] += sz[y];
    }
}

void dfs(int x) {
    for (int i = h[x]; i; i = ne[i]) {
        int y = e[i];
        if (y == fa[x]) continue;
        pre[y] = last[w[i]];
        last[w[i]] = y;
        dfs(y);
        last[w[i]] = pre[y];
        c[pre[y]] -= sz[y];
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c), add(y, x, c);
    }
    dfs1(1);
    memcpy(c + 1, sz + 1, n << 2);
    for (int x = 1; x <= n; ++x) {
        c[last[x] = n + x] = n;
    }
    dfs(1);
    for (int x = 2; x <= n; ++x) {
        res += c[pre[x]] * (LL)c[x];
    }
    printf("%lld\n", res);
    return 0;
}


新鲜事 原文

垫底抽风
7个月前
明天省选 day1。 $$\huge \text{RP++}$$。



垫底抽风
9个月前

为什么 这篇题解 并没有给出该题的解法,写的也十分粗糙,却比 这篇题解 获得的赞更高呢?



活动打卡代码 AcWing 1934. 贝茜放慢脚步

垫底抽风
10个月前
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef double DB;
const int N = 10005;
int n, d[N], t[N], szd, szt;
int main() {
  scanf("%d", &n);
  char s[2];
  for (int i = 0, x; i < n; ++i) {
    scanf("%s%d", s, &x);
    if (*s == 'T') t[szt++] = x;
    else d[szd++] = x;
  }
  sort(t, t + szt), sort(d, d + szd);
  DB v = 1, curx = 0, curt = 0;
  int i = 0, j = 0;
  while (curx < 1000) {
    DB nxt1, nxt2;
    nxt1 = nxt2 = (1000 - curx) * v;
    if (i != szd) {
      nxt1 = (d[i] - curx) * v;
    }
    if (j != szt) {
      nxt2 = t[j] - curt;
    }
    if (nxt1 < nxt2) {
      ++i;
    } else {
      ++j;
      nxt1 = nxt2;
    }
    curt += nxt1, curx += nxt1 / v;
    v += 1.0;
  }
  printf("%.0lf\n", curt);
  return 0;
}


活动打卡代码 AcWing 1960. 闪烁

垫底抽风
10个月前

$O(N \log B)$

#include <stdio.h>
#include <string.h>
typedef long long LL;
const int N = 16;
int a[N], b[N], n;
LL k;
int norm(int x) {
  return x >= n ? x - n : x;
}
int main() {
  scanf("%d%lld", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  int p = n - 1;
  while (k) {
    if (k & 1) {
      for (int i = 0; i < n; ++i) {
        b[i] = a[i] ^ a[norm(i + p)];
      }
      memcpy(a, b, n << 2);
    }
    k >>= 1;
    p = norm(p << 1);
  }
  for (int i = 0; i < n; ++i) {
    printf("%d\n", a[i]);
  }
  return 0;
}



垫底抽风
10个月前
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 20005;
int n, a[N], b[N], x, y, z, res;
int diff[N << 1], sz;
int s[N << 1];
int main() {
  scanf("%d%d%d%d", &n, &x, &y, &z);
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", a + i, b + i);
    diff[sz++] = a[i], diff[sz++] = b[i];
  }
  diff[sz++] = -1;
  sort(diff, diff + sz), sz = unique(diff, diff + sz) - diff;
  for (int i = 0; i < n; ++i) {
    a[i] = lower_bound(diff, diff + sz, a[i]) - diff;
    b[i] = lower_bound(diff, diff + sz, b[i]) - diff;
    s[0] += x, s[a[i]] += y - x, s[b[i] + 1] += z - y;
  }
  int res = 0;
  for (int i = 1; i <= sz; ++i) {
    s[i] += s[i - 1];
    if (s[i] > res) res = s[i];
  }
  printf("%d\n", res);
  return 0;
}