5 月
NOIP 2018 模拟 Day2：
ending：给定一棵 \(n\) 个点的树，边权 \(w\in\{0,1\}\)。求出有多少个三元组 \((i,j,k)\)，满足 \(dist(i,j),dist(i,k)>0\)。\(1\le n\le 10^5\)。
题解：
若 \(w(i,j)=0\)，则将 \(i,j\) 合并进一个连通块内。对于一个连通块，设其大小为 \(size\)，则对于该连通块内的一个节点 \(i\)，满足 \(dist(i,j)=0\) 或 \(dist(i,k)=0\) 的三元组 \((i,j,k)\) 的数量为 \((size-1)(size-2)+2(size-1)(n-size)\)。
那么 \(ans=n(n-1)(n-2)-\sum size((size-1)(size-2)+2(size-1)(n-size))\)。
时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int N = 1e5+10;
int n, ans, p[N], siz[N];
int check(int w) {
while (w) {
if (w % 10 != 4 && w % 10 != 7) return 0;
w /= 10;
}
return 1;
}
int find(int x) {
if (p[x] != x) return find(p[x]);
return x;
}
void merge(int u, int v) {
int fu = find(u), fv = find(v);
if (fu == fv) return ;
siz[fv] += siz[fu], p[fu] = fv;
return ;
}
signed main() {
// freopen("ending.in", "r", stdin);
// freopen("ending.out", "w", stdout);
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) p[i] = i, siz[i] = 1;
int u, v, w;
for (int i = 1; i < n; ++i) {
scanf("%lld%lld%lld", &u, &v, &w);
w = check(w);
if (!w) merge(u, v); // 分割成内部不能到达的连通块
}
for (int i = 1; i <= n; ++i) {
if (i != find(i) || siz[i] < 2) continue ;
int size = siz[i];
ans += size*(size-1)*(size-2) + size*(size-1)*(n-size)*2;
}
printf("%lld\n", n*(n-1)*(n-2)-ans);
return 0;
}
/*
10
1 2 8
1 3 7
3 4 47
5 7 23
4 6 4
6 10 747
8 6 57
9 3 447
9 5 88
566
*/