标签：题目 短路 09 给定 2023 15 times10 prod 复杂度
Vasya and a Tree
- 题目描述：给定一颗n个点、点带权的树，根节点为1，初始时所有点的点权为0。有m次操作，每次操作给定三元组(v,d,x)，将v子树中与v距离不超过d的所有点（包括点v）的点权加x。询问m次操作后所有点的点权。
- 数据范围：\(1\le n,m\le 3\times10^5\)。
做的时候一直在想怎么用树上启发式合并做，没想到正解，实际上正解更简单。
一种很朴素的想法是利用一个累加Tag，在v处加上x，在v子树中所有距离为d+1的后代减去x，然后做一个树上前缀和即可。在此基础上，我们发现所有有用的信息都在每个点的深度上，而与具体的点关系不大，因此我们在dep[v]打上+x标记，在dep[v]+d-1打上-x标记即可。最后由于不同子树之间信息不相关，逆处理回溯一下就好。
根据上述思路，需要一个支持单点修改、求前缀和的数据结构，用树状数组就可轻松完成。
时间复杂度\(O(n\log n)\)。
Buy a Ticket
- 题目描述：给定一个n个点m条边的无向图，点有点权\(a_i\)，边有边权\(w_j\)。令d(x,y)表示点x到点y的最短路，对\(\forall i\in[1,n]\)，求\(\min\limits_{j=1}^n\{2d(i,j)+a_j\}\)。
- 数据范围：\(2 ≤ n ≤ 2\times10^5, 1 ≤ m ≤ 2\times10^5\)。
非常巧妙的建图方法。新建一个源点，对所有点连一条边权为\(a_i\)的边，再将原本的边权乘2，以源点为起点跑最短路即可。
一个突发奇想：如果不允许\(j=i\)的话，在做最短路的同时做次短路，如果最短路等于\(a_i\)就用次短路。
时间复杂度\(O((n+m)\log n)\)。
Counting Arrays
- 题目描述：有q次询问，每次给定两个整数x和y，计算满足\(\prod_{i=1}^yf_i=x\)的序列\(\{f_n\}\)共有多少个（序列长为y，且\(\forall i\in[1,y],f_i\)是整数）。对于两个序列\(\{a_n\}\)和\(\{b_n\}\)，两者不同当且仅当\(\exists i\in[1,y],a_i\ne b_i\)。答案对\(10^9+7\)取模。
- 数据范围：\(1 ≤ q ≤ 10^5, 1 ≤ x, y ≤ 10^6\)。
首先解决正负数的问题，由于无论正负，都可以只乘一次就变成正，因此前(y-1)个数的符号可以任取，只需要最后一个数调整即可。因此我们可以只考虑正数，最后乘上\(2^{y-1}\)的系数即可。
这种类型的题目肯定与质因数分解有关，记\(x=\prod_{i=1}^mp_i^{k_i}\)，由于质因数之间是独立的，可以将每个质因数单独考虑。对于\(p_i^{k_i}\)，相当于把这\(k_i\)个数分配到\(y\)个位置上（根据题目说明是有序的\(y\)个位置），一个位置上可以没有数。那么根据隔板法，相当于(y-1)个隔板和\(k_i\)个数的组合数，即答案是\(C(k_i+y-1,y-1)\)，总答案即为
\[2^{y-1}\prod_{i=1}^m\binom {k_i+y-1} {y-1}
\]时间复杂度\(O(q\sqrt x)\)，可以用线性筛预处理一下大素数以防达到\(\sqrt x\)的上限。
关于组合数的一点复习：
- n个相同小球放入m个不同盒子，允许空盒：C(n+m-1,m-1)，不允许空盒：C(n-1,m-1)。
标签：题目,
短路,
09,
给定,
2023,
15,
times10,
prod,
复杂度
From： https://www.cnblogs.com/seketsu/p/17707525.html