标签 - 树链剖分

树链剖分 可持久化线段树    2016-12-30 21:22:53    390    0    0


树链剖分 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
树链剖分 tarjan 问题转化    2016-10-06 18:55:58    361    0    0

题意:有一个有点权的无向图,两种操作分别为修改一个点的点权或查询两点之间所有路径上的所有点权的最小值。 

n,m,q100000.

 

先考虑不带修改操作

点双缩点,然后把割点单独提出来,和相邻点双连通分量连边

然后就变成树了!

预处理每个bcc/割点的最小值,然后问题转化为求两点路径间的最小值,可以树链剖分/LCT.

 

对于修改操作,用set维护节点的最小值,如果修改的是割点的话,就同时用答案更新每个与它相连的bcc.

然后复杂度就萎掉了...

发现一个性质:bcc连的一定是割点,割点连的一定是bcc。 

 

那么:

修改割点的同时,只更新他的父亲bcc。 
若查询的lca是bcc,那么要查询他父亲那个割点。 

 

#include <bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>

#pragma GCC optimize("O2")
#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef __gnu_pbds::priority_queue<int, greater<int>, __gnu_pbds::pairing_heap_tag> heap;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class t> inline bool chkmin(t &x, t y) { return x > y ? x = y, true : false; }
templ