题目描述

原题地址:洛谷

由于某些原因,我不想在COGS上刷题了,于是转战洛谷。

用此题练习一下倍增LCA。

阅读全文

数论

  • 拓欧
  • 线性筛
  • 求欧拉函数
  • 组合数
阅读全文

题目描述

题目地址:COGS

这题真是蛇,调一晚上。。码力太弱了qwq

思路

本来以为这跟HAOI2016的食物链一样,但是在WA了一次后注意到食物链计算的是经过某点的路径条数,而本题是经过某边的路径条数。

DP 方程

为了求出经过某一条边的的路径条数,可以这样:

设$f(u,v)$是经过边$u,v$的路径条数,$dp(u)$为从源点到$u$的路径条数,$rdp(v)$为从$v$到终点的路径条数,则有 $f(u,v)=dp(u)\times rdp(v)$ 最后的答案就是$\max{f(u,v)} u,v\in G$

阅读全文