1 条题解
-
3
题目 大意:
给出一颗 个结点的树,每个结点上有
N
,O
,I
三个字母其中一个。一个NOI
三元组"定义为:三个分别为N
,O
,I
的结点,且O
结点在N
结点和I
结点的路径上。求NOI
三元组的个数,对 取模。考虑钦定一个点为根,记录以每个点为根的子树内
N
和I
的个数,这个通过 dfs 就可以求出。在记录总共有多少个N
和I
, 这样就可以求出这个点子树外的N
和I
的个数。接下来枚举中间点O
,扫一遍即可。具体的,每次枚举到一个
O
时,遍历所有子树,记录之前遍历到的所有子树N
和O
的数量,那么这个与前面的子树内的点匹配的贡献就珂以直接相乘算出。与后面子树内的点的贡献将在后面计算,这样就可以做到不重不漏。不懂的话可以看代码理解 Qwq。
CODE :
#include <bits/stdc++.h> using namespace std; #define MxN 100010 #define p 1000000007 int n, a[MxN], hd[MxN], res = 0, tot = 0, N[MxN], I[MxN], sN = 0, sI = 0, f[MxN]; struct node { int y, to; node(int y = 0, int to = 0) : y(y), to(to) {} }e[MxN * 2]; void add(int x, int y) { e[++ tot] = node(y, hd[x]), hd[x] = tot; } void dfs(int x, int fa) { f[x] = fa; if (a[x] == 1) N[x] = 1; else if (a[x]) I[x] = 1; for (int i = hd[x]; i; i = e[i].to) { int y = e[i].y; if (y == fa) continue; dfs(y, x); N[x] += N[y], I[x] += I[y]; } } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i ++) { char c; cin >> c; if (c == 'O') a[i] = 0; if (c == 'N') a[i] = 1, sN ++; if (c == 'I') a[i] = 2, sI ++; } for (int i = 1, x, y; i < n; i ++) { cin >> x >> y, add(x, y), add(y, x); } dfs(1, 0); for (int i = 1; i <= n; i ++) { if (a[i]) continue; int tN = 0, tI = 0; for (int j = hd[i]; j; j = e[j].to) { int y = e[j].y; if (y == f[i]) continue; (res += N[y] * tI) %= p, tI += I[y]; (res += I[y] * tN) %= p, tN += N[y]; } (res += (sN - tN) * tI) %= p; (res += (sI - tI) * tN) %= p; } cout << res << endl; return 0; }
- 1
信息
- ID
- 196
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 17
- 已通过
- 12
- 上传者