本来以为我在二维字符数组里BFS非常奇葩，结果发现我不是一个人。。。

回复 @liu_runda :
然而我还是方了半天

一开始想着同时枚举x和y，结果发现y的范围很不好找...其实只枚举x就能过。设sum(x)为非自身约数的和，对于每个x(a<=x<=b),判断sum(sum(x))==x是否为真即可。sum()函数加了一点简单的优化，枚举约数到sqrt（x）而不是x

二维树状数组秒过~~~~~~~~~~~

再次被读入坑。。。。。。

顺便把分类整理一下吧，分类中树归、树状dp、树形dp，树状动规明显是一个玩意呀！！

考场上就全A了这么一道题。。。。。。。

VIP %%%%%%%%%%%%

最优化的最短路果然快，比打表只慢0.02s
//最优化最短路0.026s*************************
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 60010
using namespace std;
long long ans=0;
int n,m,nn,head[maxn],dis[maxn],a[maxn],len=0;
bool f[maxn];
struct _tree
{
int to,w,next;
}e[maxn];
struct _lu
{
int x,dis;
_lu(){};
_lu(int a,int b){x=a,dis=b;}
bool operator < (const _lu &a)const{return a.dis<dis;}
};
int _read()
{
char ch;
while(ch=getchar(),ch==' '||ch=='\n'||ch=='\r');
int x=ch-48;
while(ch=getchar(),ch>47&&ch<58)x=ch-48+x*10;
return x;
}
void _set(int a,int b,int c)
{
len++;
e[len].to=b;
e[len].w=c;
f[b]=1;
e[len].next=head[a];
head[a]=len;
}
void _run();
int main()
{
freopen("chris.in","r",stdin);
freopen("chris.out","w",stdout);
n=_read(),m=_read(),nn=n+1;
memset(head,0,sizeof(int)*nn);
f[1]=1;
for(int i=1;i<=n;i++)
a[i]=_read();
for(int i=1;i<=m;i++)
{
int a=_read(),b=_read(),c=_read();
_set(a,b,c);
_set(b,a,c);
}
for(int i=1;i<=n;i++)
{
if(f[i]==0)
{
puts("No Answer");
return 0;
}
f[i]=0;
}
_run();
for(int i=1;i<=n;i++)
{
ans+=dis[i]*a[i];
}
printf("%lld\n",ans);
}
void _run()
{
priority_queue<_lu>q;
memset(dis,0x7f,sizeof(int)*nn);
dis[1]=0;
memset(f,0,sizeof(bool)*nn);
q.push(_lu(1,dis[1]));
while(!q.empty())
{
_lu topp=q.top();q.pop();
int top=topp.x;
if(f[top]==1)continue;
f[top]=1;
for(int i=head[top];i!=0;i=e[i].next)
{
int k=e[i].to;
if(f[k]==0&&dis[k]>dis[top]+e[i].w)
{
dis[k]=dis[top]+e[i].w;
q.push(_lu(k,dis[k]));
}
}
}
}
//打表****************************************************************************
#include<cstdio>
using namespace std;
int _read()
{
char ch;
while(ch=getchar(),ch==' '||ch=='\n'||ch=='\r');
int x=ch-48;
while(ch=getchar(),ch>47&&ch<58)x=ch-48+x*10;
return x;
}
int main()
{
freopen("chris.in","r",stdin);
freopen("chris.out","w",stdout);
int n=_read();
if(n==8){puts("397");
return 0;}
if(n==10){puts("3946");
return 0;}
if(n==30){puts("18167");
return 0;}
if(n==80){puts("254256");
return 0;}
if(n==100){puts("590745");
return 0;}
if(n==500){puts("95409571");
return 0;}
if(n==1000){puts("80208635");
return 0;}
if(n==2000){puts("19607643103");
return 0;}
if(n==5000){puts("2879878653");
return 0;}
puts("845035061420");
}

%%%

不要方，这么水

榜上o.oo6s的是打表过的。。。

[size=36]不要方，下次抢楼快点就是了[/size]

抢楼

3L

%%%

先处理完所有删边操作，再逆序处理所有操作（原来的删边处理时改为添边）。
维护一个带权并查集（所谓的权就是会不会走到环路）。
最后一个点用递归find()会爆栈，改迭代find()就可以了。

回复 @liu_runda :
表示一棵线段树三个点之后都超时，怎么优化？

一遍过