Problem K. 树上问题
378QAQ 有一棵由 $n$ 个节点组成的无根树，节点编号从 1 到 $n$，每个节点有一个正整数点权。 378QAQ 认为一个节点是美丽节点，当且仅当该节点作为根时，对于除根节点以外的所有节点，其点权都不小于其父亲节点的点权的 $\frac{1}{2}$。 请你计算出有多少个节点是美丽节点。
本题测试点包含多组数据。 第一行包含一个正整数 $t$（$1 \leq t \leq 10^4$），表示数据组数。 对于每组数据： 第一行包含一个正整数 $n$（$1 \leq n \leq 10^5$），表示节点数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^6$），表示编号为 $i$ 的节点点权。 之后 $n - 1$ 行，每行包含两个正整数 $u, v$（$1 \leq u, v \leq n$, $u \neq v$），表示无根树中存在一条连接节点 $u$ 和节点 $v$ 的边。 保证单个测试点中所有数据的 $\sum n \leq 10^5$。
Output
对于每组数据，输出一个非负整数，代表美丽节点的数量。
Solving
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
64
65
|
const int M = 1e6+100;
struct Edge
{
int to,next;
};
// Tarjan 算法来寻找有向图中的强连通分量，并进行缩点。
struct SCC { ... ... };// SCC中边的数量初始化的问题 !!
void solve()
{
int n;
cin >> n;
SCC scc(n);
vector<int> val(n+1);
for(int i=1;i<=n;i++) cin >> val[i];
for(int i=1;i<=n-1;i++)
{
int u,v;
cin >> u >> v;
if(2 * val[u] >= val[v]) // 如果满足题意可以建边则建有向边
{
scc.addEdge(v,u);
}
if(2 * val[v] >= val[u])
{
scc.addEdge(u,v);
}
}
// 易得同一个强连通分量中的各个相邻点可以互为父亲，所以可以进行缩点
vector<int> comp = scc.work();
unordered_map<int,int> mp;
for(int i=1;i<=n;i++) // 记录每个强连通分量里的原始点数目
{
mp[comp[i]]++;
}
vector<int> ind(scc.cnt,0);
// 对缩点后的DAG建边求出入度
for(int u=1;u<=n;u++)
{
for(int i=scc.head[u];i;i=scc.edge[i].next)
{
int v = scc.edge[i].to;
int cu = comp[u];
int cv = comp[v];
if(cu != cv) ind[cv]++;
}
}
// 若美丽节点存在，缩点后的DAG一定是全联通的，即存在一个强连通分量为DAG的父亲节点
// 其余均为子节点，正式的来说，即DAG中仅存在一点入度为0，其余入度均为1
// 答案即为作为父亲强连通分量节点中原始节点的数目
int zerocount = count(ind.begin()+1,ind.end(),0);
if(zerocount>1) // 若不满足只有一个强连通分量为根节点 答案为0
{
cout << 0 << endl;
return;
}
for(int i=1;i<scc.cnt;i++)
{
if(ind[i]==0)
{
// 否则找到入度为0的强连通分量点，输出答案
cout << mp[i] << endl;
break;
}
}
}
|