Brief description :

动态维护树中两点之间路径上边权的最大值。

Tags: Classical

Analysis :

经典问题.. . 树链剖分 300- 行，3.10+ s
动态树 150- 行。。。 2.90+ s…

（目前 Yang Zhe 作业里的 全局平衡二叉树 还不知道怎么实现。>_<。）

树链剖分（。。过去的写法。。。3s+-。。。
上面是我最开始时的写法。。写的非常小心谨慎。。。上来就分别对结点、边、路径各定义了一组结构体。。。（Vertex, Edge, Path … 然后全程指针指来指去。。
点和边各有一个 host 指针。。（点寄宿在边上。。边寄宿在重路径上。。。
。。路径的本体是一棵线段树，（。。为了刷榜还特地写成了自下向上维护的形式。（因为有剪枝。。。。
。然后记录其最高点的 Vertex 的指针。。（。head。。（。。跳链和询问的时候计算 offset 都要用到。。。
。。

树链剖分（。。。现在的写法。。3s+-。。。
.. 只保留的 path 这一个结构体。。直接记录每个点所在的路径。。。

/** ` Micro Mezzo Macro Flation — Overheated Economy ., **/

#include
#include
#include
#include
#include

using namespace std;

#define REP(i, n) for (int i=0;i inline void RD(T &);
template inline void OT(const T &);
template inline T& _RD(T &x){ RD(x); return x;}
inline void RS(char *s){scanf(“%s”, s);}
template inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template inline void RST(T &A){memset(A, 0, sizeof(A));}
template inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template inline void CLR(T &A){A.clear();}
template inline void checkMax(T &a,const T b){if (b>a) a=b;}
inline int _1(int i){return 1< inline void RD(T &x){char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= ‘0’; c = getchar()) x = x * 10 + c – ‘0’;}
template inline void OT(const T &x){printf(“%d\n”, x);}
template inline T max(T a, T b, T c){return max(max(a, b), c);}
/* …………………………………………………………………………………………………………………. */
const int N = 10001, M = 2 * N;

int l[N], r[N], p[N], w0[N], w1[N]; bool rt[N];
// Link-cut tree
int hd[N], nxt[M], a[M], b[M], w[M], h[M/2];
// Adjacent list

int n, ans;

#define lx l[x]
#define rx r[x]

inline void Update(int x){
w1[x] = max(w1[lx], w1[rx], w0[x]);
}

inline void Set(int l[], int y, int x){
l[y] = x, p[x] = y;
}

inline void Rotate(int x){
int y = p[x], z = p[y];

if (!rt[y]) Set(y == l[z] ? l : r, z, x);
else p[x] = z;

if (x == l[y]) Set(l, y, rx), Set(r, x, y);
else Set(r, y, lx), Set(l, x, y);

if (rt[y]) rt[y] = false, rt[x] = true; //rt[0] = true;
Update(y); //Update(x);

}

inline void Splay(int x){
while (!rt[x]) Rotate(x);
}

void Access(int x){
int y = 0; do{
Splay(x);
rt[rx] = true, rt[rx = y] = false, Update(x);
x = p[y = x];
} while (x);
}

// public:

void Query(int x, int y){
Access(y), y = 0; do{
Splay(x); if (!p[x]) OT(max(w1[rx], w1[y]));
rt[rx] = true, rt[rx = y] = false, Update(x);
x = p[y = x];
} while (x);
}

void Modify(int x, int val){
Splay(x), w0[x] = val;
}

#define v b[i]
#define w w[i]

inline void dfs(int u = 1){
for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
p[v] = u, w0[v] = w, dfs(h[i>>1] = v);
}
}

#undef x
#undef w

int main(){

//freopen(“in.txt”, “r”, stdin);
//freopen(“out.txt”, “w”, stdout);
//ios::sync_with_stdio(false);

Rush{
// Initializing Phase …

FOR_C(i, 2, _RD(n) << 1){ RD(a[i], b[i], w[i]), a[i|1] = b[i], b[i|1] = a[i], w[i|1] = w[i]; nxt[i] = hd[a[i]], hd[a[i]] = i; ++i; nxt[i] = hd[a[i]], hd[a[i]] = i; } FLC(rt, true), p[1] = -1, dfs(), p[1] = 0; // Interaction Phase ... int a, b; char cmd[5]; while (true){ RS(cmd); if (cmd[0] == 'C') RD(a, b), Modify(h[a], b); else if (cmd[0] == 'Q') RD(a, b), Query(a, b); else break; } // Rececling .... RST(hd, p, l, r); } } [/cpp]

External link:

https://www.spoj.com/problems/QTREE/

Posted by xiaodao
Category: SPOJ
Tags: 动态树