标签 - 最小生成树

树链剖分 zkw线段树 图论 好题 最小生成树    2016-10-25 21:51:44    143    0    0

Problem

雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为Wi。
如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于|Wu-Wv|,这条道路就是安全的。如果城市u和v之间存在两条没有重复道路的安全路径(其中每一段道路都是安全的),则认为这两座城市之间有着良好的贸易关系。
最近,雪之女王因为情感问题,她的能量产生巨大的波动。为了维持雪之国度的经济贸易,她希望你能帮忙对Q对城市进行调查。对于第j对城市uj和vj,她希望知道在保证这两座城市之间有着良好贸易关系的前提之下,自己最少需要保持多少的能量。
N≤100,000 Q≤500,000

Solution

因为最小生成树是最小瓶颈生成树,我们建出最小生成树,然后就只要再有一条路径了
在最开始时,将所有边权设为+∞,表示不联通
每加入一条边(u,v,w),就把路径(u,v)上的边权与w取min
询问的答案就是(qu,qv)上边权的最大值

可以用树链剖分维护
比较卡常,线段树用zkw+lc即可

Source code

  1. /*{{{*/
  2. #include <bits/stdc++.h>
  3. #ifdef __linux__
  4. #define getchar getchar_unlocked
  5. #define putchar putchar_unlocked
  6. #endif
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  10. string program_name = __FILE__;
  11. string iput = program_name.substr(0, program_name.length() - 4) + ".in";
  12. string oput = program_name.substr(0, program_name.length() - 4) + ".out";
  13. template <class T> inline bool