这道题目的大意是，一棵树上，某些边是幸运边。然后 (i, j, k) 表示从顶点 i 到顶点 j 的路径上有幸运边，从顶点 i 到顶点 k 的路径上也有幸运边，问 (i, j, k) 这样的三元组有多少个。注意 i, j, k 是有序的。

如果一条边的权值，用 10 进制表示，只含有数字 4 或 7, 那么这条边是幸运边。

原题地址：http://codeforces.com/problemset/problem/109/C

输入数据第一行表示有几个顶点，从第二行开始，有顶点减一条边，三个数 a, b, c 表示边 (a, b) 权值是 c.

样例输入 1:

4
1 2 4
3 1 2
1 4 7

样例输出 1:

16

样例输入 2:

4
1 2 4
1 3 47
1 4 7447

样例输出 2:

24

我的想法是，首先计算一个数组，lucky[u][v] 表示顶点 u 和 v 之间的路径存在幸运边。我感觉这个数组可以在 O(n2) 的时间内构造出来。

然后弄一个二重循环：

1
2
3
4
5
6
7
8
9
int result = 0;
for (int i = 0; i < n; ++i) {
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
        if (lucky[i][j])
            ++cnt;
    }
    result += cnt * (cnt - 1);
}

最后 result 就是结果。

以上代码未经测试，不保证正确性。

刚才看了一下别人的代码，发现根本无需构造 lucky[u][v] 这样的数组，因为这个数组给出的信息“太多”了。

大牛们的代码写得都非常“简洁”，有的人写变量名不超过 2 个字符，看了很多不同的人的代码发现几乎思路都是一样的，然后从不同的人起的变量和函数名中发现了道理。

其实我们可以把所谓幸运边割掉，然后一棵树就成了几个连通分量。从任意两个连通分量中分别取任意两个顶点，这两个顶点之间的路径原来肯定都是经过幸运边的。然后我们要求的就是各个连通分量和各个连通分量之间的顶点个数，通过并查集的辅助，我们可以实现。

计算三元组个数的时候，可以这样想：对于某个连通分量中的一个顶点，它可以和其余连通分量中的任何顶点相连，路径中包含幸运边。设 n 是所有顶点的个数，c[i] 是第 i 个连通分量中顶点的个数，那么如果将 c[i] 中的某个元素作为三元组中的第一个元素，可以有 c[i] * A2n-c[i] = c[i] * (n – c[i]) * (n – c[i] – 1) 种方案。然后将所有连通分量的这个值加起来就是结果了。

我只能说编程无止境啊……

以下内容追加于 2011-11-08 00:33:00 …

很久不写并查集，犯了一点 SB 错误。提交了 3 次才 AC…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef unsigned long long ull;

const size_t N = 100000;

struct dsu_t
{
    size_t p[N], c[N];

    inline void reset(size_t n) {
        for (size_t i = 0; i < n; ++i) {
            p[i] = i; c[i] = 1;
        }
    }

    inline size_t root(size_t x) {
        return x == p[x] ? x : (p[x] = root(p[x]));
    }

    inline void join(size_t x, size_t y) {
        size_t a = root(x), b = root(y);
        if (a != b) {
            c[b] += c[a]; c[a] = 0; p[a] = b;
        }
    }
};

inline bool islucky(size_t x) {
    while (x) {
        size_t r = x % 10;
        if (r != 4 && r != 7) return false;
        x /= 10;
    }
    return true;
}

dsu_t dsu;

int main(int argc, char *argv[])
{
    size_t n; cin >> n;
    ull result = 0; dsu.reset(n);
    for (size_t i = 1; i < n; ++i) {
        size_t u, v, w;
        cin >> u >> v >> w;
        if (!islucky(w)) dsu.join(--u, --v);
    }
    for (size_t i = 0; i < n; ++i)
        dsu.root(i);

    for (size_t i = 0; i < n; ++i)
        if (dsu.c[i])
            result += ull(dsu.c[i])
                    * ull(n - dsu.c[i])
                    * ull(n - dsu.c[i] - 1);
    cout << result << endl;
    return EXIT_SUCCESS;
}

原创文章，转载请注明来源：http://euyuil.com/2694/codeforces-109c-lucky-tree/