【详●析】危险路径
一道爆零的题。。。
【问题描述】
给定一个\(n\)个点，\(m\)条边的连通无向图，点从\(1\)~\(n\)编号，而每条边有一个危险值。
对于任意一条路径，定义路径上危险值的最大值为这条路径的危险值。
对于任意不同的两点\(u\)和\(v\)，定义\(d(u, v)\)为所有从\(u\)到\(v\)的路径的危险值最小值。
对于每个点\(u\)，定义\(f_{u}=\sum_{1 \leq v \leq n, u \neq v} d(u, v)\)，表示点\(u\)的危险程度。
你的任务就是计算每个点的危险程度。
为了便于输出，你只需要给出 \(ans=\oplus_{i=1}^{n}(i \cdot f(i))\)的值即可，其中 \(\oplus\) 代表按位异或。
每个测试点包含多组数据（\(1 \leq T \leq 200\)），对于每组数据：\(1 \leq n \leq 10^{5}, n-1 \leq m \leq 3 \times 10^{5}, 1 \leq u, v \leq n, 0 \leq w \leq 10^{9}\)。
注意，任意两点可能直接连有多条边，而且边的两个端点可能相同。
【分析】
考试时这道题爆零了。。。忘了处理多组数据情况。。。虽然也是暴力分。
首先要把题意给弄懂。
举个简单栗子，如图一，按照题意的描述，首先，直接不考虑自环（想想为什么），然后，从图中可以看出，\(1\)到\(4\)有两条路径，取路径中最大值的最小值，即为\(22\)，所以\(d(1, 4)=22\)，同样的，\(d(1, 3)=35\), \(d(1, 5)=35\), \(d(1, 2)=78\)。
理解了题意，那么暴力算法就可以得出了。我们直接用\(Floyd\)的\(O(n^3)\)把所有点之间的最短路给求出来，然后累加\(f_i\)，最后计算\(ans\)。其中，只需要在\(Floy\)算法中的操作中如此松弛：
\[ d[i][j]=min(max(d[i][k], d[k][j]), d[i][j]) \]
于是\(20pt\)到手。当然，你用\(n\)遍\(SPFA\)也行叭，反正时间复杂度也只能优化到\(O(n^2logn)\)，可以多过一个点。
现在想想如何优化？或者说，这道题有什么我们还没看出来的性质呢？
还是看着图一，我们想，\(1\)与\(4\)有两条路径，又因为我们需要路径上的最大危险值尽量的小，所以危险值为\(43\)的这条路径必然会被我们所抛弃，因为通过它能到达的点，危险值为\(22\)的路径也能到达，且比它危险值更小，所以我们大可以把它给删掉。同样的，\(3\)到\(4\)中，危险值为\(65\)的这条路径也必然会被我们抛弃，当我们把所有不需要的边删掉后，我们会惊奇地发现整个图会变成一棵树！
变成树后再拉伸一下，是不是变得友好多了？
为什么会变成一棵树？因为在完成删边操作后，每两个点之间必然有且只有唯一一条简单路径。如果有多条路径，说明什么？只能说你没删完~
如果图变成了这样一棵树，然后呢？
很好想啊，在树上继续暴力，对每个点\(dfs\)一次，统计答案，时间复杂度为\(O(n^2)\)。
那怎么建成这棵树呢？想想我们的去边操作：如果\(a\)到\(b\)有路径的危险值比当前路径的危险值更小，就抛弃它。（好残忍啊\(QAQ\)），换句话说，我们只取每两个点之间危险值最小的路径。
想到了什么？没错，最小生成树！
没学过最小生成树可以看补一补，也许以后我也会写一篇。。。也许会咕咕咕。。。
这道题用\(Krukal\)算法是最爽的，至于为什么，后面再讲。
于是我们便可以\(O(nlog n)\)以边值排序，再\(O(n)\)建树，建树好后\(O(n^2)\)遍历统计，总的时间复杂度也就是\(O(n^2)\)，\(50pt\)到手。
现在开始讲正解吧。
想想我们\(50pt\)的做法，建树时我们每次连边的操作，对于答案的统计有什么贡献呢？仔细想想。
如图三，假设我们正在连危险值为\(76\)的这条边。我们能知道对统计答案会产生怎样的贡献吗？
设正在连的边的权值为\(w\)，连接的两个端点为\(x\)和\(y\)，用\(size[a]\)表示当前节点\(a\)所在的联通块中的点数，十分显然的是，\(x\)所在的联通块上所有点\(f_i\)会累加上\(size[y]*w\)，\(y\)所在的联通块上所有点\(f_i\)会累加上\(size[x]*w\)。
为什么？
很好理解，因为我们是按边权值由小到大连边，所以我们正连的边的权值一定大于它左右两个端点所在两个联通块中所有边的权值，所以要想从当前一个联通块中的\(u\)点走到当前另一个联通块的\(v\)点去，\(d(u, v)\)必定为我们正在连的边的权值。然后因为有\(size[v]\)个点，所以乘起来，反之亦然。
再加一条新边呢？同样的处理呀。
这时\(1\)所在联通块在加入危险值为\(76\)的边后发生了变化，但同样的，\(1\)所在的联通块上所有点\(f_i\)会累加上\(size[5]*88\)，\(5\)所在的联通块上所有点\(f_i\)会累加上\(size[1]*88\)。
这样经过建边操作后，\(f_i\)就出来啦。
正确性是十分显然的。
可现实总是很骨感。。。。也许你已经发现了，有很多问题等待着我们去处理。。。
比如说，我们如何动态统计\(size[i]\)？我们怎么知道每次加边时左右端点所在联通块中所有点的编号？
好，我们来想一想解决方案，当然，这不是唯一的，后面会提到。
首先，我们在建边操作中不可能统计出来答案，因为在建边中根本不可能以低耗时动态求得联通块中每个点的编号。我们只能在建树后统计答案。
建树后，我们从边权最大的开始删边，每删一次边，用前面的思想进行统计答案，当把最后一条边删完后，答案统计就结束了。很容易知道，这与前面建边中统计答案的操作是等价的。
可是这又存在不好统计\(size\)的问题。而且还有很多几乎无法实现的细节。除了暴力。。。
那么，解决方案呢？
我们可以知道，我们正在连的一条边其实可以连在它左右端点所在联通块中的任意一点上，比如图四，我偏不让\(1\)和\(5\)相连，我让\(4\)和\(5\)相连，对答案统计完全没有影响。
再进一步理解，每当两个联通块或点连接好后，我们可以把它们视为一个联通块或者一个点。只不过，我们需保留联通块内原有的信息。
于是，直接给出新的建树操作：
对于每一个连边操作\(u, v\)，如果可以连，那么就新建一个虚节点\(s\)，把使\(s\)分别与\(u\),\(v\)连接，并\(tag[u]=size[v]*w\),\(tag[v]=size[u]*w\)，其中,\(tag[a]\)表示当前\(a\)所在联通块中所有\(f_i\)分别累加\(tag[a]\)，便于统计。同时使\(size[s]=size[u]+size[v]\)，更新联通块中点数。对于图四，我们便可构造这样的一棵树。
这棵树有什么性质呢？
- 必定是棵二叉树。（很好理解的）
- 只有叶节点是实点。
- 从根节点遍历，所经过的边权单调下降。（我们是从边最小的开始建树的，发现每个节点的权值肯定大于等于它子树中任意一个点的权值，因此构造最小生成树的时候越大的边出现的越晚，对应建立的点深度也越浅）
这些性质有什么用呢？
我们可以得出：每个点对应子树里都是边长小于等于它的点权的联通块。
这样，就能满足我们从边权最大的开始遍历的要求，同时也能很好地计算\(size\)。
那怎么统计答案呢？
我们从根节点\(x\)出发，向下\(dfs(x, val)\)遍历，实质就是按边权从大到小遍历。然后每走到一个节点\(to\)，便\(val+=tag[to]\)，累加。如果到达叶节点，直接\(f[to]=val+tag[to]\)。自己手模拟一遍大概就会懂了。
其实，这就是克鲁斯卡尔重构树算法。
以下摘自：
在克鲁斯卡尔求最短路的基础上对原来的图进行一定的修改，与克鲁斯卡尔求最短路的区别在于每当找到一条树边时，将其变成一个点，这个点连接这条边连接的两个联通块（的根节点），然后就可以得到一棵树，这棵树的叶子结点，其余节点都是树边，权值就是树边的长度。
当然，你也可以照我前面讲的那样理解。
克鲁斯卡尔重构树常被用来快速求树上两点路径最大值的最小值，也许还会有其他的应用。。。
这下你知道为什么我们最好用\(Krukal\)了吧？
后来问了问\(P\)姓\(dalao\)，他说\(Prim\)也能做，只不过要用\(LCT\)动态维护\(size\)和其他的一些信息%%%。。。
于是，这道题就可以\(A\)了。
哦，对了，记得开\(ull\)。
【Code】
#include#include #include #include #define ll unsigned long longusing namespace std;const int INF = 0x7fffffff;const int N = 1000000 + 15;inline int read(){ int f = 1, x = 0;char ch; do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0'||ch>'9'); do {x = x*10+ch-'0'; ch = getchar(); } while (ch >= '0' && ch <= '9'); return f*x;}inline void open() { freopen("dangerous.in","r",stdin); freopen("dangerous.out","w",stdout);}inline void close() { fclose(stdin); fclose(stdout); }struct tree { int to, nxt;}tr[N]; struct sakura { int u, v; int w;}sak[N];inline bool cmp(sakura a, sakura b) { return a.w < b.w; }ll tag[N], size[N], f[N], ans;int T, n, m, fa[N], head[N], cnt, node;inline void add(int a, int b) { ++cnt; tr[cnt].to = b, tr[cnt].nxt = head[a], head[a] = cnt;}inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }inline void init() { node = n, cnt = 0; memset(head, 0, sizeof (head)); memset(tag, 0, sizeof (tag)); for (int i = 1;i <= n; ++i) fa[i] = i, f[i] = 0, size[i] = 1;}inline void dfs(int u, ll val) { for (int i = head[u];i;i = tr[i].nxt) { int to = tr[i].to;// printf("tag : %d || %d -> %d\n", tag[to], u, to); if (to <= n) f[to] = val + tag[to]; dfs(to, val + tag[to]); }}int main(){ open(); T = read(); while (T--) { n = read(), m = read(); init(); for (int i = 1;i <= m; ++i) { sak[i].u = read(), sak[i].v = read(), sak[i].w = read(); } sort(sak + 1, sak + 1 + m, cmp); for (int i = 1;i <= m; ++i) { int u = sak[i].u, v = sak[i].v, w = sak[i].w; if (find(u) == find(v)) continue;// printf("%d -- %d : %d\n", u, v, w); int x = find(u), y = find(v); tag[x] = size[y] * w; tag[y] = size[x] * w; add(++node, x); add(node, y); fa[x] = fa[y] = fa[node] = node; size[node] = size[x] + size[y]; }// printf("------------\n"); dfs(node, tag[node]);// printf("------------\n");// for (ll i = 1;i <= n; ++i) printf("%d ", f[i]); ans = 0; for (int i = 1;i <= n; ++i) { ans ^= (1ull * i * 1ull * f[i]); } printf("%lld\n", ans); } close(); return 0;}
喂，你不是说还有其他方法吗？
没错，还有一种，在遍历时实时更新\(tag[x]\)，思想和上面的差不多，只不过细节和代码实现比较难一点。。。这里，机房另一位神犇给出了代码，大家可以访问他的。