[HDU6430]TeaTree

没想到bitset的时间复杂度能够降到这种地步。

题目大意:给你一棵有$n$个节点,根节点为$1$的树,每个节点都有一个值$value[i]$,对于任意两个节点$i,j$,它们会告诉他们的$LCA$一个值$gcd(value[i],value[j])$,问最后每个节点所能听到的最大值为多少,若没有则输出$-1$。

TeaTree

点击查看原题面

Recently, TeaTree acquire new knowledge gcd(Greatest Commen Divisor), now she want to test you.
As we know, teaTree is a tree and her root is node 1, she have n nodes and n-1 edges, for each node i, it has it’s value v[i].
For every two node i and j(i is not equal to j), they will tell their Lowest Commen Ancestors(LCA) a number:gcd(v[i],v[j]).
For each node, you have to calculate the max number that it heard. some definition:
In graph theory and computer science, the lowest commen ancestor(LCA) of two nodes u and v in a tree is the lowest(deepest) node that both u and v as descendants, where we define each node to be a descendant of itself.

Input:
On the first line, there is a positive integer n, which describe the number of nodes.
Next line there are n-1 positive integers f[2], f[3], …, f[n], f[i] describe the father of node i on tree.
Next line there are n positive integers v[2], v[3], … , v[n], v[i] describe the value of node i.
n <=100000, f[i]<i, v[i]<=100000

Output:
Your output should include n lines, for i-th line, output the max number that node i heard.
For the nodes who heard nothing, output -1.

Sample Input

4
1 1 3
4 1 6 9

Sample Output

2
-1
3
-1

经过观察就能看出来,对于一个节点,它听到的值即为其本身及每棵与其直接相连的子树中任挑两个集合,每个集合中再挑出一个值所得到的最大的$gcd$。

首先我们可以知道的是,$gcd(i,j)$一定为$i,j$的因子,因此我们可以将问题转化成求两个集合中均出现过的最大的因子,这一步我们可以用一个$bitset$来标记,$bitset[i]=1$即为这棵子树中有至少一个数的因子为$i$,然后用$dfs$的方法传参,计算出每棵子树中存在的所有因子。

在求交时,我们可以用$bitset$的内置函数$_Find_first()$,找出$bitset$中第一个为$1$的元素的位置,由于无法求最后一个,因此我们只能将因子倒过来放,然后进行求解。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>vec[maxn];
int a[maxn];
int ans[maxn];
bitset<maxn> dfs(int x){
bitset<maxn> cur(0),mid;
for(int i=1;i*i<=a[x];i++){//求本身的因子
if(a[x]%i==0){
cur[maxn-i]=1;
cur[maxn-a[x]/i]=1;
}
}
int res=0;
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
mid=dfs(y);
res=max(res,maxn-(int)(cur&mid)._Find_first());//求最大的因子
cur|=mid;//合并集合
}
if(res) ans[x]=res;
return cur;
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d",&x);
vec[x].push_back(i);
}
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
memset(ans,-1,sizeof(ans));
dfs(1);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------