BZOJ 2152:聪聪可可(树上点分治)
2024-09-21 18:38:00
题意
中文题意。
思路
和上一题类似,只不过cal()函数需要发生变化。
题目中要求是3的倍数,那么可以想到 (a + b) % 3 == 0
和 (a % 3 + b % 3) % 3 == 0
是一样的,因此,我们只要在每次计算路径长度的时候,把 dis[u]%3
放在一个桶里面,然后就可以转化为,一个简单的计数问题了。
tong[0]
对于答案的贡献:就像题目中一共有n^2个点对一样,一开始包括根结点本身1个点,有多少条路径,就有多少个点,因此是 tong[0]^2
。
tong[1] 和 tong[2]
对于答案的贡献:每个长度为1的路径,都可以和每个长度为2的路径匹配,而且因为是点对,(2,3)和(3,2)算两种,所以乘2。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, nxt, w;
} edge[N*2];
int dis[N], son[N], f[N], vis[N], tot, head[N], tong[3], root, sum, ans;
void Add(int u, int v, int w) {
edge[tot] = (Edge) { v, head[u], w }; head[u] = tot++;
edge[tot] = (Edge) { u, head[v], w }; head[v] = tot++;
}
void getroot(int u, int fa) {
son[u] = 1; f[u] = 0;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if(vis[v] || v == fa) continue;
getroot(v, u);
son[u] += son[v];
f[u] = max(f[u], son[v]);
}
f[u] = max(f[u], sum - son[u]);
if(f[u] < f[root]) root = u;
}
void getdeep(int u, int fa) {
tong[dis[u]]++;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v, w = edge[i].w;
if(vis[v] || v == fa) continue;
dis[v] = (dis[u] + w) % 3;
getdeep(v, u);
}
}
int cal(int u, int now) {
dis[u] = now;
memset(tong, 0, sizeof(tong));
getdeep(u, 0);
// printf("tong %d : %d, %d, %d\n\n", u, tong[0], tong[1], tong[2]);
// 就像题目中一共有n^2个点对一样,一开始包括根结点本身1个点,有多少条路径,就有多少个点,因此是tong[0]^2
int res1 = tong[0] * tong[0];
// 对于每个长度为1的路径,都可以和每个长度为2的路径匹配,而且因为是点对,(2,3)和(3,2)算两种,所以乘2
int res2 = tong[1] * tong[2] * 2;
return res1 + res2;
}
int work(int u) {
// int now = cal(u, 0);
ans += cal(u, 0);
// ans += now;
// printf("work %d : %d\n\n", u, now);
vis[u] = 1;
for(int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v, w = edge[i].w;
if(vis[v]) continue;
int now = cal(v, w);
// printf("delete %d -> %d : %d\n\n", u, v, cal(v, w));
ans -= cal(v, w);
sum = son[v];
getroot(v, root = 0);
// printf("root : %d\n\n", root);
work(root);
}
}
int main() {
int n;
while(~scanf("%d", &n)) {
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
Add(u, v, w % 3);
}
sum = n, ans = root = 0, f[0] = INF;
getroot(1, root);
work(root);
// ans += n;
// printf("ans : %d\n", ans);
int tol = n * n;
int g = __gcd(ans, tol);
printf("%d/%d\n", ans / g, tol / g);
}
return 0;
}
/*
5
1 2 1
1 3 2
1 4 1
2 5 3
8
1 2 1
2 5 3
1 4 1
4 6 2
1 3 2
3 7 2
7 8 3
*/
最新文章
- Fedora 22中的日期和时间配置
- 手机APP创建桌面快捷方式
- Ubuntu 网络参数设置
- C#中try catch中throw ex和throw方式抛出异常有何不同
- isstream例子
- 【HDU 3709】 Balanced Number (数位DP)
- CSS3属性text-overflow(省略符)实战开发详解
- 基于raw os 的事件触发系统
- [html5] 学习笔记-bootstrap介绍
- 推荐两款Windows管理工具
- Beta第二天
- IntelliJ IDEA 2017.3/2018.1激活与汉化
- go语言之进阶篇关闭channel
- 一款easyUI写的界面例子,小记
- git 找回 git reset --hard HEAD 后的代码
- JAVA邻接矩阵实现拓扑排序
- linux中压缩、解压缩命令详解
- 【QTP专题-优化】VBS脚本启动QTP并运行测试
- Dart基础
- Go测试,功能测试,性能测试,测试辅助,go test 工具,高级测试,IO相关测试,黑盒测试,HTTP测试,进程测试
热门文章
- WPF 属性变更通知类的实现
- javascript高程笔记-------第四章 变量、作用域和内存问题
- C/C++使用libcurl库发送http请求(get和post可以用于请求html信息,也可以请求xml和json等串)
- Delphi多线程下的ADO编程
- PySide——Python图形化界面入门教程(五)
- 微信小程序把玩(十三)progress组件
- Entity Framework的查询
- Android Java调用Qt写的so库
- Qt在各平台上的搭建qt-everywhere(Qt for windows7-64bit, Ubuntu 12.04-32bit, 嵌入式x86平台, 嵌入式arm平台)
- PHP开发框架 Laravel