传送门：https://www.51nod.com/Challenge/Problem.html#problemId=1588

题意

定义幸运数字只由4和7组成，比如4，7，47。

给一棵树，要我们找到三元组(i,j,k)，两两之间的路径中必须要有一条由幸运数字组成的边。

问，存在多少组这样的三元组。

思路

幸运数字好处理，check一下。关键是怎么找出贡献。

统计树上方案数，一般先固定一个点，比如i，然后再找另外两个点j和k，算出i这个点对应的贡献。

设f[u]为以u为根节点的子树中，有几个点到u的路径中存在幸运数字。
设h[u]为以u为根节点的子树外，有几个点到u的路径中存在幸运数字。

这样，我们的j和k的选择就可以在f中选择，或者h中选择，或者f和h中选择。

即i的贡献为$f[i]*(f[i]-1)+h[i]*(h[i]-1)+f[i]*h[i]*2$

然后就是处理f和h。

dfs过程中：

• 如果u和v的边是幸运数字，则$f[u]+=siz[v]$
• 否则$f[u]+=f[v]$
• 如果v和u的边是幸运数字，则$h[v]+=siz[1]-siz[v]$
• 否则$h[v]+=h[u]+f[u]-f[v]$

所以要先dfs一遍预处理f和siz，然后dfs一遍处理h，最后统计方案。

Code

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;

struct Edge {
    int v, w;
};
vector<Edge> g[N];

ll f[N], h[N];
int siz[N];

void dfs1(int u, int fa) {
    siz[u] = 1;
    for(auto e : g[u]) {
        int v = e.v;
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(e.w) f[u] += siz[v];
        else f[u] += f[v];
    }
}

void dfs2(int u, int fa) {
    for(auto e : g[u]) {
        int v = e.v;
        if(v == fa) continue;
        if(e.w) h[v] = siz[1] - siz[v];
        else h[v] = h[u] + f[u] - f[v];
        dfs2(v, u);
    }
}

int check(int n) {
    while(n) {
        if(n % 10 != 4 && n % 10 != 7) return 0;
        n /= 10;
    }
    return 1;
}

void solve() {
    int n; cin >> n;
    for(int i = 1;i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        w = check(w);
        g[u].push_back(Edge{v, w});
        g[v].push_back(Edge{u, w});
    }
    dfs1(1, -1);
    dfs2(1, -1);
    ll ans = 0;
    for(int i = 1;i <= n; i++) ans += f[i] * (f[i] - 1) + h[i] * (h[i] - 1) + f[i] * h[i] * 2;
    cout << ans << endl;
}

signed main() {
    solve();
}