题目地址：BZOJ 2152 找有多少对权值和为3的倍数的点。最简单的点分治。 代码如下：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) //#pragma comment(linker, /STACK:1024000000) const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=20000+10; int head[MAXN], cnt, root, ans, min1; int siz[MAXN], ha[4], dep[MAXN], vis[MAXN]; struct node { int v, w, next; }edge[MAXN<<1]; void add(int u, int v, int w) { edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; } void init() { memset(head,-1,sizeof(head)); cnt=ans=0; memset(vis,0,sizeof(vis)); } void getroot(int u, int fa, int s) { siz[u]=1; int i, max1=0; for(i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||vis[v]) continue ; getroot(v,u,s); siz[u]+=siz[v]; max1=max(max1,siz[v]); } max1=max(max1,s-siz[u]); if(min1>max1){ root=u; min1=max1; } } void getdep(int u, int fa) { ha[dep[u]%3]++; siz[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==fa||vis[v])continue ; dep[v]=dep[u]+edge[i].w; getdep(v,u); siz[u]+=siz[v]; } } int Cal(int u, int len) { dep[u]=len; ha[0]=ha[1]=ha[2]=0; getdep(u,-1); return ha[0]*ha[0]+ha[1]*ha[2]*2; } void work(int u) { vis[u]=1; ans+=Cal(u,0); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(vis[v]) continue ; ans-=Cal(v,edge[i].w); min1=INF; getroot(v,-1,siz[v]); work(root); } } int gcd(int x, int y) { return x==0?y:gcd(y%x,x); } int main() { int n, u, v, w, i, j, _gcd; while(scanf(%d,&n)!=EOF){ init(); for(i=1;i
?