luogu3953 逛公园

题解

与路径统计很像的一道题。

设$f[i][k]$为起点到$i$点,距离与到其的最短路偏差(肯定大于$d[i]$,$d[i]$为$1$到$i$的最短路)为$k$时的路径数。

然后可以拓扑排序后按照$k$从小到大的对每个点进行$dp$:

设有边$(u,v,w)$,转移方程可以写成$f[v][d[u]+w+k-d[v]]+=f[u][k]$

顺序很重要,需要先枚举$k$然后再枚举点和边。
继续阅读

luogu1084 疫情控制

$\texttt{loj}$上也有(2607),数据稍微强一点,需要卡一下常(可能是我自带大常数)。

题意

$N$个城市组成一棵树,$1$号节点是首都,也是根节点。$M$个军队驻扎在某些城市上,军队可移动,从一个点移动到邻接点花费的时间为边权;也可以原地驻扎,但是不能驻扎在首都。求最少的时间,可以将调度军队使得从每个叶子节点到根节点的路径上都有驻军。

$2≤m≤n≤50,000$
继续阅读