【BZOJ 2152】 聪聪可可

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2152

【算法】

点分治

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 20010 int i,n,u,v,w,ans1,ans2,g,tot,len,root;
int head[MAXN],size[MAXN],weight[MAXN],d[MAXN],sum[MAXN];
bool visited[MAXN]; struct Edge
{
int to,w,nxt;
} e[MAXN<<]; inline int gcd(int x,int y)
{
if (y == ) return x;
else return gcd(y,x % y);
}
inline void addedge(int u,int v,int w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline void getroot(int u,int fa,int total)
{
int i,v;
size[u] = ;
weight[u] = ;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (v != fa && !visited[v])
{
getroot(v,u,total);
size[u] += size[v];
weight[u] = max(weight[u],size[v]);
}
}
weight[u] = max(weight[u],total - size[u]);
if (weight[u] < weight[root]) root = u;
}
inline void dfs(int u,int fa)
{
int i,v,w;
d[++len] = sum[u];
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (v != fa && !visited[v])
{
sum[v] = (sum[u] + w) % ;
dfs(v,u);
}
}
}
inline int calc(int u)
{
int i;
int ret = ;
int cnt[];
memset(cnt,,sizeof(cnt));
len = ;
dfs(u,);
for (i = ; i <= len; i++) cnt[d[i]]++;
for (i = ; i <= len; i++) ret += cnt[( - d[i]) % ];
return ret;
}
inline void work(int u)
{
int i,v,w;
visited[u] = true;
sum[u] = ;
ans1 += calc(u);
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!visited[v])
{
sum[v] = w % ;
ans1 -= calc(v);
root = ;
getroot(v,,size[v]);
work(root);
}
}
} int main()
{ scanf("%d",&n);
for (i = ; i < n; i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
memset(visited,false,sizeof(visited));
size[] = weight[] = n;
getroot(,,n);
ans1 = ;
ans2 = n * n;
work(root);
g = gcd(ans1,ans2);
ans1 /= g; ans2 /= g;
printf("%d/%d\n",ans1,ans2); return ;
}
上一篇:ASP.NET MVC+EF框架+EasyUI实现权限管理系列(18)-过滤器的使用和批量删除数据(伪删除和直接删除)


下一篇:ASP.NET MVC+EF框架+EasyUI实现权限管理系列(17)-注册用户功能的细节处理(各种验证)