BZOJ 2152 & 点分治

Description:

  只是打法法塔前测试一下板子

Code:

  

/*=================================
# Created time: 2016-04-20 14:35
# Filename: 2152.cpp
# Description:
=================================*/
#define me AcrossTheSky&HalfSummer11
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define Abs(x) ((x) > 0 ? (x) : (-(x)))
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 100005
#define maxm 100005
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num){
num = 0; bool f = true;char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();}
while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();}
num = f ? num: -num;
}
int outs[100];
template<class T> inline
void write(T x){
if (x==0) {putchar('0'); putchar(' '); return;}
if (x<0) {putchar('-'); x=-x;}
int num=0;
while (x){ outs[num++]=(x%10); x=x/10;}
FORM(i,num-1,0) putchar(outs[i]+'0');
}
/*==================split line==================*/
int n,m,mn,root,cnt,ans,sume=0;
bool vis[maxn];
struct Edge{int to,next,w;} e[maxm];
int first[maxn],sz[maxn],dep[maxn],d[maxn];
inline int gcd(int a,int b) { return b==0?a:gcd(b,a%b);}
inline void addedge(int x,int y,int w){
sume++; e[sume].to=y; e[sume].w=w;e[sume].next=first[x]; first[x]=sume;
}
inline int getroot(int x,int fa,int sum){
sz[x]=1; int mx=0,y; //`vis[x]=true;
for (int i = first[x];i;i=e[i].next)
if (!vis[y=e[i].to] && e[i].to!=fa){
getroot(y,x,sum);
sz[x]+=sz[y];
mx=max(mx,sz[y]);
}
mx=max(mx,sum-mx);
if (mx<mn) mn=mx,root=x;
}
inline void getdep(int x,int fa){
dep[++cnt]=d[x]; int y;
for (int i=first[x];i;i=e[i].next)
if (!vis[y=e[i].to] && e[i].to!=fa){
d[y]=d[x]+e[i].w;
getdep(y,x);
}
}
inline int cal(int x,int last=0){
int c[3]; memset(c,0,sizeof(c));
cnt=0; d[x]=last;
getdep(x,-1);
FORP(i,1,cnt) c[dep[i]%3]++;
return c[0]*c[0]+(c[1]*c[2])*2;
}
inline void dfs(int x,int sum){
vis[x]=true;
ans+=cal(x); int y;
for (int i=first[x];i;i=e[i].next) if (!vis[y=e[i].to]){
ans-=cal(y,e[i].w);
int s=sz[y]>sz[x]?sum-sz[x]:sz[y];
root=0; mn=INF; getroot(y,x,s);
dfs(root,s);
}
}
int main(){
read(n);
FORP(i,1,n-1) {
int x,y,z; read(x); read(y); read(z);
addedge(x,y,z%3); addedge(y,x,z%3);
}
memset(vis,false,sizeof(vis));
mn=INF;
getroot((n+1)>>1,-1,n);
dfs(root,n);
int down=n*n,t=gcd(ans,down);
write(ans/t); putchar('/'); write(down/t); puts("");
}
上一篇:POJ 2082Lost Cows<>


下一篇:控制台——对WIN32 API的使用(user32.dll)