大意: 给定树, 随机选两点, 求两点距离是3的倍数的概率.

树形dp入门水题, 枚举每个点作为lca时的答案即可.

#include <iostream>
#include <queue>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} const int N = 1e6+10;
int n, dp[N][3];
struct _ {int to,w;};
vector<_> g[N];
ll ans; void dfs(int x, int fa, int d) {
for (int i=0; i<g[x].size(); ++i) {
int y = g[x][i].to;
if (y==fa) continue;
dfs(y,x,(d+g[x][i].w)%3);
ans += 2ll*dp[y][d];
REP(i,0,2) ans += 2ll*dp[x][i]*dp[y][(2*d-i+3)%3];
REP(i,0,2) dp[x][i] += dp[y][i];
}
++dp[x][d],++ans;
} int main() {
scanf("%d", &n);
REP(i,2,n) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
w %= 3;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0,0);
ll x = ans, y = (ll)n*n, z = gcd(x,y);
x /= z, y /= z;
printf("%lld/%lld\n", x,y);
}

最新文章

  1. String和Date、Timestamp之间的转换
  2. Hive 字符串操作[转]
  3. C# 如何用多个字符串来切分字符串并去除空格
  4. md5应用
  5. android studio我的习惯操作
  6. C语言 函数理解(以数组做参数)
  7. Web前端性能优化之图片优化
  8. Python常用函数笔记
  9. vector中的元素删除
  10. HTTP权威指南----缓存
  11. Android 签名(1)为什么要签名
  12. gd库复制图片做水印
  13. SQL Server 2012 案例教程(贾祥素)——学习笔记
  14. ubuntu系统备份与恢复(也适用于其他linux系统)
  15. s21day22 python笔记
  16. CM记录-操作系统调优
  17. while练习题
  18. echarts中间有字饼图Demo2
  19. Dawn开源项目
  20. 弹出层框架layer快速使用

热门文章

  1. 深入分析JAVA IO(BIO、NIO、AIO)
  2. 访问项目时报错org.apache.jasper.JasperException: java.lang.NullPointerException
  3. Python JSON dump ,load,dumps,loads
  4. CloudFlare 新手入门中文教程
  5. C#winform和百度API互动-----之JS读取中C#中的函数
  6. LC 955. Delete Columns to Make Sorted II
  7. DriverManager
  8. 阶段5 3.微服务项目【学成在线】_day05 消息中间件RabbitMQ_6.RabbitMQ研究-入门程序-消费者
  9. JAVA NIO学习笔记二 频道和缓冲区
  10. 小程序签名MD5加密