记录编号	266697	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]白树黑	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.777 s
提交时间	2016-06-09 09:50:46	内存使用	234.54 MiB

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<algorithm>
#define ll long long
#define mod 1000007
inline void in(int&x){for(x=getchar();x<48|x>57;x=getchar());x^=48;for(int tmp=getchar();47<tmp&tmp<58;tmp=getchar())x=x*10+(tmp^48);}
int n,mx,shu,first[200010];
long long ans;
struct edge{int v,w,nx;}o[400010];
int num[50000010];
inline void add(int u,int v,int w){
	o[++shu].v=v,o[shu].w=w,o[shu].nx=first[u],first[u]=shu;
}
int shu1,first1[mod],shu2,first2[mod];
struct hash{int u,nx;ll v;}o1[mod],o2[mod];
inline void add1(int u,int v){
	int ha=u%mod;
	o1[++shu1].u=u,o1[shu1].v=v,o1[shu1].nx=first1[ha],first1[ha]=shu1;
}
inline void add2(int u,ll v){
	int ha=u%mod;
	o2[++shu2].u=u,o2[shu2].v=v,o2[shu2].nx=first2[ha],first2[ha]=shu2;
}
bool flag[10010];
int p[5010];
inline void get_p(int N){
	for(int i=2;i<=N;++i){
		if(!flag[i])p[++p[0]]=i;
		for(int j=1;j<=p[0]&&i*p[j]<=N;++j){
			flag[i*p[j]]=1;
			if(!(i%p[j]))break;
		}
	}
}
inline void dfs(int x,int last,int HASH){
	int ha=HASH%mod;bool ok=0;
	for(int i=first1[ha];i;i=o1[i].nx)
	    if(o1[i].u==HASH){
			ans+=o1[i].v,++o1[i].v,ok=1;
			break;
	    }
	if(!ok)add1(HASH,1);
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==last)continue;
		int tmp=0,tap=o[i].w;
		for(int j=1;j<=p[0]&&tap!=1;++j){
			if(tap%p[j])continue;
			int tip;ha=p[j]%mod,ok=0;
			for(int k=first2[ha];k;k=o2[k].nx)
			    if(o2[k].u==p[j]){
					tip=o2[k].v,ok=1;
			    }
			if(!ok)add2(p[j],tip=rand()*rand()*rand()*rand());
			while(!(tap%p[j]))tmp^=tip,tap/=p[j];
		}
		if(tap!=1){
			int tip;ha=tap%mod,ok=0;
			for(int k=first2[ha];k;k=o2[k].nx)
			    if(o2[k].u==tap){
					tip=o2[k].v,ok=1;
			    }
			if(!ok)add2(tap,tip=1ll*rand()*rand()*rand()*rand());
			tmp^=tip;
		}
		dfs(o[i].v,x,HASH^tmp);
	}
}
int main(){
	freopen("E_Tree.in","r",stdin);
	freopen("E_Tree.out","w",stdout);
	srand(time(0));
	in(n);
	for(int i=1,u,v,w;i<n;++i){
		in(u),in(v),in(w),add(u,v,w),add(v,u,w);
		if(w>mx)mx=w;
	}
	get_p(sqrt(mx));
	dfs(1,1,0);
	printf("%lld",ans<<1);
}