描述
尽管付出了种种努力，jzp还是得过光棍节。
jzp非常不爽，但也无能为力，只能够哀叹起来他的命运。他想到了一位长者的人生经验：“人的一生，不光要靠自我奋斗，也要考虑历史的进程”。
他终于明白自己只是时运不济，所以又继续开始努力。终于在圣诞节当天把到了妹子。
jzp从此过上了快乐的现充生活，在圣诞节当天，他还和妹子玩起了有趣的游戏：
jzp的家里有一棵非常大的圣诞树，可以看成是一个n个点的无向联通无环图。每个点上都有一个正整数，JZP和妹子每次都会选择树上的一条路径，
这条路径的权值被定义为路径上所有点上数的最大公约数，JZP可以得到这个权值的分数。
JZP玩了一会儿有点腻了，他想知道对于每种可能的权值x，权值为x的不同路径的数量（a到b的路径和b到a的路径算作一种，a到a自身也算作一条路径。）
解题报告:
用时2h30min，N TLE
这题不难，直接暴力点分，复杂度可以证明是对的，因为从一个点下去，gcd只有可以是它的约数，所以是(sqrt n)的，所以直接去重之后两重循环枚举，复杂度是(O(n))的，所以复杂度是对的。但是本人太渣，点分都可以写错，找重心的数组一直没清空(那么居然是0.7s是怎么回事？)然后一交就TLE，还以为是常数太大，就一直在压，浪费了许久，写了两个代码，一个是所有方案-不合法的，另一个是用vector维护已经处理过的子树的gcd，处理完当前子树后，在处理另一个子树直接用当前子树的每一个gcd和vector里的元素匹配.
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,val[N],head[N],num=0,nxt[N<<1],to[N<<1],sum;
void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
bool vis[N];int sz[N],root=0,son[N]={N};
il int gi(){
RG int str=0;RG char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')
str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
il void getroot(int x,int last){
int u;sz[x]=1;son[x]=0;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
getroot(u,x);
sz[x]+=sz[u];son[x]=Max(son[x],sz[u]);
}
son[x]=Max(son[x],sum-sz[x]);
if(son[x]<son[root])root=x;
}
il int gcd(int x,int y){
int c;while(x%y){c=y;y=x%y;x=c;}
return y;
}
vector<int>q,s;ll t[N],ton[N];
void count(int x){
int szz=q.size(),gc;
for(int i=0;i<szz;i++){
gc=gcd(q[i],x);
t[gc]+=ton[q[i]];
}
}
int app[N];
il void calc(int x,int last,int g){
int u;
t[g]++;count(g);
if(!app[g])s.push_back(g);app[g]++;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
if(g!=1)calc(u,x,gcd(val[u],g));
else calc(u,x,1);
}
}
il void solve(int x){
int u,szz;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(vis[u])continue;
calc(u,x,gcd(val[u],val[x]));
szz=s.size();
for(int j=0;j<szz;j++){
if(!ton[s[j]])q.push_back(s[j]);
ton[s[j]]+=app[s[j]];app[s[j]]=0;
}
s.clear();
}szz=q.size();
for(int i=0;i<szz;i++)ton[q[i]]=0;
q.clear();
}
il void dfs(int x){
int u;vis[x]=true;solve(x);
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(vis[u])continue;
root=0;sum=sz[u];getroot(u,x);
dfs(root);
}
}
void work()
{
int x,y,lim=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
val[i]=gi();
lim=Max(lim,val[i]);
t[val[i]]++;
}
for(int i=1;i<n;i++){
x=gi();y=gi();
link(x,y);link(y,x);
}
sum=n;root=0;getroot(1,1);
dfs(root);
for(int i=1;i<=lim;i++)
if(t[i])printf("%d %lld
",i,t[i]);
}
int main()
{
work();
return 0;
}
再是原来写的，清空数组后也能过
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,val[N],head[N],num=0,nxt[N<<1],to[N<<1],sum;
void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}
bool vis[N];int sz[N],root=0,son[N]={N};
il int gi(){
RG int str=0;RG char ch=getchar();
while(ch>'9' || ch<'0')ch=getchar();
while(ch>='0' && ch<='9')
str=(str<<1)+(str<<3)+ch-48,ch=getchar();
return str;
}
il void getroot(int x,int last){
int u;sz[x]=1;son[x]=0;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
getroot(u,x);
sz[x]+=sz[u];son[x]=Max(son[x],sz[u]);
}
son[x]=Max(son[x],sum-sz[x]);
if(son[x]<son[root])root=x;
}
il int gcd(int x,int y){
int c;while(x%y){c=y;y=x%y;x=c;}
return y;
}
struct node{
int x;ll cnt;
bool operator <(const node &Pr)const{return x<Pr.x;}
}q[N];
int top=0;bool flag=false;
il void calc(int x,int last,int g){
int u;
if(g==1 && flag){q[++top].x=1;q[top].cnt=sz[x];return ;}
if(top && q[top].x==g)q[top].cnt++;
else q[++top].x=g,q[top].cnt=1;
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(u==last || vis[u])continue;
if(g!=1)calc(u,x,gcd(val[u],g));
else calc(u,x,1);
}
}
ll t[N];
il void solve(int x,int op,int sta){
top=0;calc(x,x,sta);
int Yut=top;top=1;
sort(q+1,q+Yut+1);
RG int i,j;
for(i=2;i<=Yut;i++){
if(q[i].x==q[top].x)q[top].cnt+=q[i].cnt;
else q[++top]=q[i];
}
int tmp;
for(i=1;i<=top;i++){
t[q[i].x]+=q[i].cnt*(q[i].cnt-1)*op>>1;
for(j=i+1;j<=top;j++){
tmp=gcd(q[i].x,q[j].x);
t[tmp]+=q[i].cnt*q[j].cnt*op;
}
}
}
il void dfs(int x){
int u;vis[x]=true;
flag=false;solve(x,1,val[x]);
for(int i=head[x];i;i=nxt[i]){
u=to[i];if(vis[u])continue;
root=0;sum=sz[u];getroot(u,x);
flag=true;solve(u,-1,gcd(val[x],val[u]));
dfs(root);
}
}
void work()
{
int x,y,lim=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
val[i]=gi();
lim=Max(lim,val[i]);
t[val[i]]++;
}
for(int i=1;i<n;i++){
x=gi();y=gi();
link(x,y);link(y,x);
}
sum=n;root=0;getroot(1,1);
dfs(root);
for(int i=1;i<=lim;i++)
if(t[i])printf("%d %lld
",i,t[i]);
}
int main()
{
work();
return 0;
}