P9593 「Daily OI Round 1」Block

题目描述

给定一棵树，节点有颜色，在树上距离为 $2$ 的点连边（仍保留原来的边），求新图中颜色相同且连通的非空点集数量。由于答案可能非常大，您只需输出答案对 $10^9+7$ 取模的值。

点集连通的定义：对于图 $G(V,E)$，$V$ 的一个子集 $V^{\prime }$ 是连通点集，当且仅当 $G(V^{\prime },E^{\prime })$ 是一个连通图，其中边集 $E^{\prime }=\{(u,v)|(u,v)\in E\wedge u\in V^{\prime }\wedge v\in V^{\prime }\}$。

输入格式

第一行一个正整数 $n$，表示节点个数。

接下来一行 $n$ 个正整数，第 $i$ 个正整数 $c_i$ 表示第 $i$ 个节点的颜色。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示原树有一条 $u$ 到 $v$ 的边。

输出格式

一行一个整数，表示答案对 $10^9+7$ 取模的值。

输入输出样例 #1

输入 #1

4
1 2 1 1
1 2
2 3
2 4

输出 #1

8

输入输出样例 #2

输入 #2

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

输出 #2

14

输入输出样例 #3

输入 #3

16
1 1 2 1 1 2 2 2 1 1 2 1 1 1 2 1
12 8
14 9
10 8
1 16
7 12
6 1
14 8
3 1
12 5
1 13
12 2
1 12
15 8
11 5
4 12

输出 #3

442

输入输出样例 #4

输入 #4

16
11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
4 14
4 15
12 13
2 5
7 15
10 2
15 8
15 13
9 11
13 11
3 15
8 16
6 13
1 4
10 4

输出 #4

27454

输入输出样例 #5

输入 #5

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

输出 #5

16

说明/提示

样例 1 中，原树如下图所示：

树上距离为 $2$ 的点连边后，新图如下图所示：

则 $8$ 个颜色相同且连通的非空点集分别是：{1},{2},{3},{4},{1,3},{1,4},{3,4},{1,3,4}\{1\},\{2\},\{3\},\{4\},\{1,3\},\{1,4\},\{3,4\},\{1,3,4\}{1},{2},{3},{4},{1,3},{1,4},{3,4},{1,3,4}。

本题开启捆绑测试。

$\text{Subtask}$	分值	$n\le$	特殊性质	子任务依赖
$0$	$5$	$10^5$	A	无
$1$	$5$	$16$	无	无
$2$	$5$	$10^5$	B	无
$3$	$15$	$10^5$	C	无
$4$	$20$	$10^5$	D	无
$5$	$50$	$10^5$	无	$0\sim 4$

• 特殊性质 A：所有节点的颜色不相同。
• 特殊性质 B：给出的树是菊花，具体地，第 $i$ 条边连接节点 $1$ 和节点 $i+1$。
• 特殊性质 C：给出的树是链，具体地，第 $i$ 条边连接节点 $i$ 和节点 $i+1$。
• 特殊性质 D：所有节点的颜色相同。

对于全部数据，满足 $2\le n\le 10^5$，$1\le c_i\le n$。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=1e9+7;
int n,c[N],dp[N],f[N],g[N],ans;
vector<int> G[N];
void dfs(int u,int fa){
    for(int v:G[u])
		if(v!=fa)dfs(v,u);
    dp[u]=1;
    for(int v:G[u])
		if(v!=fa)
        	g[c[v]]=1ll*g[c[v]]*(dp[v]+1)%P;
    f[u]=g[c[fa]];
    for(int v:G[u])
		if(v!=fa)
        	dp[u]=1ll*dp[u]*(f[v]+dp[v]*(c[v]==c[u]))%P;
    for(int v:G[u])if(v!=fa)
        ans=(ans+g[c[v]]-1)%P,g[c[v]]=1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",c+i),g[i]=1;
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    printf("%d\n",(ans+dp[1])%P);
    return 0;
}

.

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容