根号分治
CF : https://codeforces.com/contest/1822/problem/G2
//常用头文件！
#include <bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define INF 0x3f3f3f3f //这个是int的最大值 可直接赋值
#define lINF 0x3f3f3f3f3f3f3f //这个是long long 的最大值
int t;
void solve()
{
int n;
cin>>n;
vector<i64> a(n+1);
map<i64,i64> s;
for(int i=0;i<n;i++)
{
cin>>a[i];
s[a[i]]++;
}
i64 ans=0;
for(auto [x,y]:s)
{
ans+=y*(y-1)*(y-2);
if(x<1e6)
{
for(int i = 1; i * i<= x; i ++ )
{
if(x % i == 0)
{
if(i != 1) {
if(s.count(x / i) && s.count(x * i)) ans += s[x / i] * s[x] * s[x * i];
}
int i1 = x / i;
if(i1 != i) {
if(s.count(x / i1) && s.count(x * i1)) ans += s[x / i1] * s[x] * s[x * i1];
}
}
}
}
else
{
for(int i = 1; i * x <= 1e9; i ++ ) {
if(x % i == 0) {
if(i != 1) {
if(s.count(x / i) && s.count(x * i)) ans += s[x / i] * s[x] * s[x * i];
}
int i1 = x / i;
if(i1 != i) {
if(s.count(x / i1) && s.count(x * i1)) ans += s[x / i1] * s[x] * s[x * i1];
}
}
}
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
while(t--)
{
solve();
}
}
换根dp的模板子
//常用头文件！
#include <bits/stdc++.h>
using namespace std;
typedef int64_t i64;
#define INF 0x3f3f3f3f //这个是int的最大值 可直接赋值
#define lINF 0x3f3f3f3f3f3f3f //这个是long long 的最大值
int t;
bool st[300011];
struct node {
int where;
node *next;
}*head[200011],a[400011];
i64 f[2000011][2][2],v[2000011];//记录换根树的东西！
i64 h[2000011];//记录要花费多少来换根节点
int makelist(int x,int y,int cnt)
{
a[++cnt].where=y;
a[cnt].next=head[x];
head[x]=&a[cnt];
return cnt;
}
void up(int i)
{
st[i]=1;
for(node *y=head[i];y;y=y->next)
{
if(!st[y->where])
{
up(y->where);
if(f[y->where][0][0]+1>f[i][0][0])
{
f[i][1][0]=f[i][0][0],f[i][1][1]=f[i][0][1];
f[i][0][0]=f[y->where][0][0]+1,f[i][0][1]=y->where;
}else if(f[y->where][0][0]+1>f[i][1][0])
{
f[i][1][0]=f[y->where][0][0]+1,f[i][1][1]=y->where;
}
}
}
}
void bfs(int x,int c)//必须得bfs 才能求出准确代价！！
{
vector<int> q(200015);
int rear=0,front=1;
q[++rear]=x;
// cout<<q[1];
// cout<<x;
// cout<<1;
while(front<=rear)
{
auto t=q[front++];
//cout<<t<<endl;
st[t]=1;
for(node *p=head[t];p;p=p->next)
{
if(!st[p->where])
{
q[++rear]=p->where;
h[p->where]=h[t]+c;
}
}
}
}
void down(int i)
{
st[i]=true;
for(node *x=head[i];x;x=x->next)
{
if(!st[x->where])
{
if(f[i][0][1]==x->where)
{
if(v[i]>f[i][1][0])
v[x->where]=v[i]+1;
else v[x->where]=f[i][1][0]+1;
}else {
v[x->where]=max(v[i],f[i][0][0])+1;
}
down(x->where);
}
}
}
void solve()
{
int n,k,c;
cin>>n>>k>>c;
int cnt=0;
for(int i=1;i<=n;i++)
{
f[i][0][0]=0,f[i][0][1]=0;
f[i][1][0]=0,f[i][1][1]=0;
head[i]=0;
h[i]=0;
st[i]=0;
v[i]=0;
}
// memset(f,0,sizeof(f));
// memset(v,0,sizeof(v));
// memset(head,0,sizeof(head));
// memset(st,0,sizeof(st));
// memset(h,0,sizeof(h));
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
// cout<<x<<y<<endl;
cnt=makelist(x,y,cnt);
cnt=makelist(y,x,cnt);//这里去更新cnt
//cout<<a[cnt].where;
}
bfs(1,c);//去看换根的花费！
for(int i=1;i<=n;i++)
st[i]=0;
up(1);
for(int i=1;i<=n;i++)
st[i]=0;
down(1);
i64 ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,max(f[i][0][0],max(f[i][1][0],v[i]))*k-h[i]);
}
cout<<ans<<'\n';
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
cin>>t;
while(t--)
{
solve();
}
//int i,j,k;
// __int128 a;
// a=1222;
}