标签 - tarjan

树链剖分 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