传送门 考虑离线+差分。 将∑l≤i≤rdep[LCA(i,z)]\sum _{l \le i \le r} dep[LCA(i,z)]∑l≤i≤r​dep[LCA(i,z)]转化成∑1≤i≤rdep[LCA(i,z)]−∑1≤i≤l−1dep[LCA(i,z)]\sum _{1 \le i \le r} dep[LCA(i,z)]-\sum _{1 \le i \le l-1} dep[L...

传送门 你们搞的这道题啊，exciting。 首先，看到标题我们就知道用什么算法实现，于是我们使用主席树。 容易发现，a,ba,ba,b和ccc都在同一条到根节点的链上面，而且ccc是这条链最下面的节点，但是a,ba,ba,b关系未知。 于是分类讨论： 1.b∈anc(a)1.b \in anc(a)1.b∈anc(a)，发现c∈subtree(a),dis(a,b)≤kc \in subt...

传送门 考虑预处理出szszsz数组，表示子树的大小，处理出来val[u]val[u]val[u]数组，表示uuu的子树里面的所有奶牛到uuu集合的不方便度。 于是dpdpdp就十分简单，初始化dp[1]=val[1]dp[1]=val[1]dp[1]=val[1]，然后考虑集合地点从uuu变到vvv，vvv子树里面的所有奶牛都会少走www路程，而剩下奶牛都会都走www路程。 1234567...

P3761 [TJOI2017]城市 注意到两个城市之间的最大交通费用就是树的直径。 考虑枚举删去哪一条边，假设删的是边u,vu,vu,v，那么我们发现直径可能有三种选择： 1.1.1.直径缩在蓝色子树里面。 2.2.2.直径缩在红色子树里面。 上面两种情况，我们都不能通过加边来缩短直径，是无法掌控的。 3.3.3.直径的一段在蓝色子树里面，另一端在红色子树里面，这时直径必定跨越边u,v...

传送门 将iii与aia_iai​连边，发现在一个环上的牛永远不会消失，总是在绕圈圈，所以问题转换为求这个图里面所有环的长度之和。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <b...

传送门 ProProPro 有n个城市，编号依次为1到n，同时有m条单向道路连接着这些城市，其中第i条道路的起点为Ui，终点为Vi 。(1<=Ui < Vi <= n)。 特工团队一共有3名成员：007，008，以及009，他们将要执行q次秘密任务。 在每次任务中，三人可能会处于三个不同的城市，他们互相之间通过对讲机保持联络。编号为i的城市的无线电频为Wi，如果两个城市的...

传送门 首先，大家都可以看出来，这道题是一个多重背包，设f(i)f(i)f(i)为和为iii可不可行，那么假设kkk为{an}\{a_n\}{an​}中的一个数，且f(s)==1f(s)==1f(s)==1，我们把f(s+k×1)f(s+k \times 1)f(s+k×1)，f(s+k×2)f(s+k \times 2)f(s+k×2)，f(s+k×3)f(s+k \times 3)f(s...

考虑dp\rm dpdp，其中f1[i][j]f1[i][j]f1[i][j]表示由起点到达iii，走的是路径111，路径总长度为jjj的方法可不可行，f2f2f2类似，拓扑排序的过程中大力转移即可。 转移过程类似背包问题。 好像可以用bitset\rm bitsetbitset优化，少一些常数。 注意输出IMPOSSIBLE!\rm IMPOSSIBLE!IMPOSSIBLE! 1234...

传送门 一眼看上去：这不就是最短路的模板吗？ 两眼：边权太大了，怎么开的下？ 考虑还是用Dijkstra\rm DijkstraDijkstra解决，每个点开一棵线段树，存储二进制的状态 我们要实现的功能: 1.给二进制数加上2k2^k2k，这可以看成把kkk位后所有连续的111变成0，再把所有连续111后的那一个000变成111 2.比较两个二进制数的大小，先比较高位，再比较低位。 但是用...

传送门 这道题可以用暴力水过，不用tarjantarjantarjan 思路：将奶牛看成节点，反向建边，对于一只奶牛，跑一边暴力dfsdfsdfs，判断能不能到达其他所有奶牛，然后加一些小小的剪枝就可以过了。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505...