主要思路
好题!好题!
这个题首先需要了解到一个性质:每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以,我们最后需要求的就是每个国家对应的集合的大小。
如何去快速求这个东西呢?我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来,然后算这些路径的交集。这样是一种计算的方法,但是确实不快速。
Continue reading →好题!好题!
这个题首先需要了解到一个性质:每个点所能到达的、进行贸易的国家的集合可以形成一个连通的生成子图。所以,我们最后需要求的就是每个国家对应的集合的大小。
如何去快速求这个东西呢?我们需要把 \(m\) 个路径中每个跨过当前点 \(u\) 的路径给拿出来,然后算这些路径的交集。这样是一种计算的方法,但是确实不快速。
Continue reading →这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。
Continue reading →这道题思路很妙。
发现算子只有\(+, -, \times\),所以路径上的解可以表示成线性组合:\(ax + b\)。我们记录从根到下、从下到根的线性组合前缀,然后我们考虑来利用前缀进行分割:就是树上差分的那种套路。
我们先考虑父亲边为:
大概这样合并:
void dfs(int u) { dep[u] = dep[fa[0][u]] + 1; for (int i = head[u]; i != -1; i = edges[i].nxt) if (edges[i].to != fa[0][u]) { fa[0][edges[i].to] = u, upweight[edges[i].to] = edges[i].weight; trs_up[edges[i].to] = trs_up[u], trs_down[edges[i].to] = trs_down[u]; if (edges[i].weight == 1) { trs_down[edges[i].to].b = (trs_down[edges[i].to].b + vi[edges[i].to]) % mod; trs_up[edges[i].to].b = (1LL * trs_up[u].a * vi[u] + trs_up[u].b) % mod; } else if (edges[i].weight == 2) { trs_down[edges[i].to].b = (trs_down[edges[i].to].b - vi[edges[i].to] + mod) % mod; trs_up[edges[i].to].b = (1LL * trs_up[edges[i].to].b - 1LL * trs_up[u].a * vi[u] % mod + mod) % mod; } else { trs_down[edges[i].to].a = 1LL * trs_down[u].a * vi[edges[i].to] % mod; trs_down[edges[i].to].b = 1LL * trs_down[u].b * vi[edges[i].to] % mod; trs_up[edges[i].to].a = 1LL * trs_up[edges[i].to].a * vi[u] % mod; } dfs(edges[i].to); } }
如何分裂边呢?我们只需要抵消掉\(a\)和\(b\)的效果即可,直接用逆元和减法就行了:考虑设置\(ax + b\)为从\(x\)到根的效果,设置\(cx + d\)为\(lca\)到根的效果,那么\(x\)到根的效果为\(ex + f\),可以列式为:
\[ e(cx + d) + f = ax + b \]
解出来就行了,然后再对\(y\)做差不多的处理就可以解决这道题了。(挺麻烦的,细节还挺多,不如打暴力)
我们发现,其实这道题就是要求询问无向图上点对之间的割点数量:可以确定割点的数量是唯一的,因为如果有更多的割点,那么不存在更少的割点使点双连通分量连通。
既然我们知道了大概的题意和要求,那么我们可以发现:如果把这些割点所在域内的非割点全部缩成一个点,然后让割点分别连接,那么根据「不存在更少的割点使点双连通分量连通」的「唯一性」,可以知道这样建出来的东西一定是一棵树。
这样就很好做了!直接树上差分+LCA即可。我们需要用 Tarjan 把这些点缩起来,通过割点进行连接,然后做一遍 DFS 之类的获取前缀和,再处理 LCA 倍增数组,我们就可以在线回答询问了。算法的复杂度为\(\Theta(n \log n + m \log n)\)。
这道题可以离线回答,很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息,然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG,但是我们可以动态开点,然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的,这样空间就可以接受的了。
既然有了很好用的动态开点线段树,我们就可以用树上差分那一套路,在端点和\(LCA\)处打标记,然后考虑从下往上合并答案。合并可以用线段树合并,复杂度为重合部分,差不多就是\(O(\log n)\)。然后就没了,很傻逼的一道题。
翻译一下:
给你一棵带点权的树和一堆路径,问对于每一个点\(i\)有多少条路经满足\(w(s,i) = weight(i)\)。
听起来就挺毒瘤的,是吧。根据这一类树上问题的套路,考虑把所有路径拆成\((s \to LCA(s,t))\)和\((t \to LCA(s,t))\),分开处理。我们先来处理\((s \to LCA(s, t))\)这一类问题:假设我们现在要知道路径\((s \to LCA(s, t))\)对点\(i\)的贡献,必须满足: