[题目|树形dp+GCD]Educational Codeforces Round 58-D
题目描述
You are given a tree consisting of n vertices. A number is written on each vertex; the number on vertex i is equal to ai.
Let's denote the function g(x,y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices). Also let's denote dist(x,y) as the number of vertices on the simple path between vertices x and y, including the endpoints. dist(x,x)=1 for every vertex x.
Your task is calculate the maximum value of dist(x,y) among such pairs of vertices that g(x,y)>1.
输入格式
The first line contains one integer n — the number of vertices (1≤n≤2⋅10^5).
The second line contains n integers a1, a2, ..., an(1≤ai≤2⋅10^5) — the numbers written on vertices.
Then n−1 lines follow, each containing two integers x and y(1≤x,y≤n,x≠y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.
输出格式
If there is no pair of vertices x,y such that g(x,y)>1, print 0. Otherwise print the maximum value of dist(x,y) among such pairs.
输入样例#1：
3
2 3 4
1 2
2 3
输出样例#1：
1
输入样例#2：
3
2 3 4
1 3
2 3
输出样例#2：
2
输入样例#3：
3
1 1 1
1 2
2 3
输出样例#3：
0
思想
本题是在树上dp糅合了GCD的计算，对于我来说现阶段难度稍大，大致记录一下思想。
首先这是一道树形dp题目，重点在于其dp方程是两个维度，第一维是常规的数字节点1-n，第二维（之前没有考虑到）是该数字节点对其所有子节点的所有gcd因子（若为1则不进行记录）。因为每个数对每个数的gcd是不一样的，所以开第二个维度。并且gcd满足交换律和结合律，故而可以无视前后因子顺序向上传递。
dp函数中起始时的初始化仍然要考虑，并且特判1。
下面来解决一下计数问题，即it1->second+it2->second为何就是可能的答案？
it->second是以it->first为顶点的子树中的可能gcd链长度，因为其dfs的遍历是每条支路只遍历一次的，（假设当前顶点下有几个支路）故而每次it1长度更新时只更新了之前的链+1（顶点），之后的链长即it2的长度只到顶点的子节点为止，并不进行+1操作，这也就是为什么最终结果不是it1->second+it2->second+1的原因，并且dfs的遍历也使其不会重复计数。
再来说一说为何是先求最大状态再去更新父亲节点，原理仍是dfs的遍历性质，每次遍历之后求得的最大状态是单条路径的，与后面没遍历过的支路不发生更新关系，故不会出错。通俗来讲就是走一步看一步，先算一条路然后立刻更新，然后再算下一条路再更新，如此云云。
题解
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<iostream>
#include<map>
#define M 200005
using namespace std;
const int inf=0x7f7f7f7f;
int a[M],head[M];
int deg[M];
int cnt;
int maxx;
struct edge1{
int to;
int next;
}edge[2*M];
map<int,int>dp[M]; //GCD约为log（原数）级别的数据密度，故可以进行map来使用（发挥其稀疏的优势）
map<int,int>::iterator it1,it2;
void add(int from,int to)
{
edge[cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt++;
}
int gcd(int a,int b)
{
if(a<b) swap(a,b);
return b==0?a:gcd(b,a%b);
}
void Dp(int rec,int pr) //pr->rec
{
if(a[rec]>1)
{
dp[rec][a[rec]]=1; //有bug
}
for(int i=head[rec];i!=0;i=edge[i].next)
{
int g=edge[i].to; //g是末点，rec是始点
if(g==pr) continue;
Dp(g,rec);
for(it1=dp[g].begin();it1!=dp[g].end();it1++)
{
for(it2=dp[rec].begin();it2!=dp[rec].end();it2++)
{
if(gcd(it1->first,it2->first)!=1)
{
maxx=max(maxx,(it1->second)+(it2->second));
}
}
}
for(it1=dp[g].begin();it1!=dp[g].end();it1++)
{
int tmp=gcd(it1->first,a[rec]);
if(tmp==1) continue;
dp[rec][tmp]=max(dp[rec][tmp],(it1->second)+1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
int n,c,b;
int flag=0;
cin>>n;
cnt=0;
maxx=1;
memset(deg,0,sizeof(deg));
memset(head,0,sizeof(head));
// memset(edge,0,sizeof(edge));
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=1)
flag=1;
}
for(int i=1;i<=n-1;i++)
{
cin>>c>>b;
add(c,b);
add(b,c);
}
Dp(1,1);
int max1=-1*inf;
if(!flag)
{
cout<<"0"<<endl;
}
else
{
cout<<maxx<<endl;
}
return 0;
}