【BZOJ 2152】 聪聪可可
2024-08-31 10:25:46
【题目链接】
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 ;
}
最新文章
- InnoDB引擎的索引和存储结构
- collections在java中的常见用法
- Effective C# 学习笔记(原则二:为你的常量选择readonly而不是const)
- activity传递数据
- 2875: [Noi2012]随机数生成器 - BZOJ
- POJ 1663
- 【原创】一起学C++ 之enum ---------C++ primer plus(第6版)
- bzoj 1927 [Sdoi2010]星际竞速(最小费用最大流)
- SQL Server索引进阶:第六级,标签
- 1821: [JSOI2010]Group 部落划分 Group
- redis持久化快速回忆手册
- spring auto-config
- android 控件设置透明度
- 是armhf,还是armel?
- UML和模式应用3:迭代和进化式分析和设计案例研究
- 队列queue 代码
- NPM慢怎么办 - nrm切换资源镜像
- [转载]FMS Dev Guide学习笔记(验证用户)
- pandas 初识(三)
- JS+Canvas的棋盘游戏和Java的动态结合