标签：cnt 1000005 return int 树论 t1 dep
- 在“无限”的量中寻找“有限”的量——可能产生贡献的点对的数量
- 不妨用两个log的时间复杂度进行预处理（都预处理了，就不要再想着判断合法性了）
- 1~N每个数的约数个数的总和大约为NlogN
- u,v都在某个子树内等价于它们的【最近公共祖先】在该子树内，将点对的贡献打到LCA(i,j)上
点击查看代码
#include <bits/stdc++.h>
using namespace std;
vector<int>a[1000005];
vector<int>d[100005];
int dep[1000005],s[1000005],n,tot,dfn[1000005],c[1000005];
int f[1000005][20];
int ans[1000005];
int lca(int u,int v)
{
if(dep[u]>dep[v])
{
swap(u,v);
}
for(int j=19;j>=0;j--)
{
if(f[v][j]!=0&&dep[f[v][j]]>=dep[u])
{
v=f[v][j];
}
}
if(u==v)
{
return u;
}
for(int j=19;j>=0;j--)
{
if(f[u][j]!=f[v][j])
{
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
void pre()
{
for(int j=1;j<20;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
}
void dfs(int n1)
{
dfn[n1]=++tot;
s[n1]=1;
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=f[n1][0])
{
dep[a[n1][i]]=dep[n1]+1;
f[a[n1][i]][0]=n1;
dfs(a[n1][i]);
s[n1]+=s[a[n1][i]];
}
}
}
int lowbit(int n)
{
return n&(-n);
}
void add(int n1)
{
while(n1<=n)
{
c[n1]++;
n1+=lowbit(n1);
}
}
int ask(int n1)
{
int s=0;
while(n1>0)
{
s+=c[n1];
n1-=lowbit(n1);
}
return s;
}
int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
struct t1
{
int i,j,l;
}t[3000005];
int cnt;
bool cmpt(t1 a,t1 b)
{
return a.l<b.l;
}
struct q1
{
int r,x,id;
}q[1000005];
bool cmpq(q1 a,q1 b)
{
return a.x<b.x;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
for(int i=1;i<=100000;i++)
{
for(int j=i;j<=100000;j+=i)
{
d[j].push_back(i);
}
}
int T;
cin>>T;
while(T--)
{
memset(c,0,sizeof(c));
cin>>n;
for(int i=1;i<=n;i++)
{
a[i].clear();
}
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
tot=0;
dep[1]=1;
dfs(1);
pre();
cnt=0;
for(int i=1;i<=n;i++)
{
for(int l=i;l<=100000;l+=i)
{
for(int j=0;j<d[l].size();j++)
{
if(d[l][j]>i)
{
break;
}
if(lcm(i,d[l][j])==l)
{
t[++cnt]=(t1){i,d[l][j],l};
}
}
}
}
sort(t+1,t+cnt+1,cmpt);
int Q;
cin>>Q;
for(int i=1;i<=Q;i++)
{
cin>>q[i].r>>q[i].x;
q[i].id=i;
}
sort(q+1,q+Q+1,cmpq);
int p=0;
for(int i=1;i<=Q;i++)
{
while(p+1<=cnt&&t[p+1].l<=q[i].x)
{
p++;
int tmp=lca(t[p].i,t[p].j);
add(dfn[tmp]);
if(t[p].i!=t[p].j)
{
add(dfn[tmp]);
}
}
ans[q[i].id]=ask(dfn[q[i].r]+s[q[i].r]-1)-ask(dfn[q[i].r]-1);
}
for(int i=1;i<Q;i++)
{
cout<<ans[i]<<' ';
}
cout<<ans[Q]<<endl;
}
return 0;
}
标签：cnt,
1000005,
return,
int,
树论,
t1,
dep
From： https://www.cnblogs.com/watersail/p/18346929