首页 > ACM题库 > HDU-杭电 > HDU 4010-Query on The Trees[解题报告]HOJ
2015
04-15

HDU 4010-Query on The Trees[解题报告]HOJ

Query on The Trees

问题描述 :

We have met so many problems on the tree, so today we will have a query problem on a set of trees.
There are N nodes, each node will have a unique weight Wi. We will have four kinds of operations on it and you should solve them efficiently. Wish you have fun!

输入:

There are multiple test cases in our dataset.
For each case, the first line contains only one integer N.(1 ≤ N ≤ 300000) The next N�\1 lines each contains two integers x, y which means there is an edge between them. It also means we will give you one tree initially.
The next line will contains N integers which means the weight Wi of each node. (0 ≤ Wi ≤ 3000)
The next line will contains an integer Q. (1 ≤ Q ≤ 300000) The next Q lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1. Given two integer x, y, you should make a new edge between these two node x and y. So after this operation, two trees will be connected to a new one.
2. Given two integer x, y, you should find the tree in the tree set who contain node x, and you should make the node x be the root of this tree, and then you should cut the edge between node y and its parent. So after this operation, a tree will be separate into two parts.
3. Given three integer w, x, y, for the x, y and all nodes between the path from x to y, you should increase their weight by w.
4. Given two integer x, y, you should check the node weights on the path between x and y, and you should output the maximum weight on it.

输出:

There are multiple test cases in our dataset.
For each case, the first line contains only one integer N.(1 ≤ N ≤ 300000) The next N�\1 lines each contains two integers x, y which means there is an edge between them. It also means we will give you one tree initially.
The next line will contains N integers which means the weight Wi of each node. (0 ≤ Wi ≤ 3000)
The next line will contains an integer Q. (1 ≤ Q ≤ 300000) The next Q lines will start with an integer 1, 2, 3 or 4 means the kind of this operation.
1. Given two integer x, y, you should make a new edge between these two node x and y. So after this operation, two trees will be connected to a new one.
2. Given two integer x, y, you should find the tree in the tree set who contain node x, and you should make the node x be the root of this tree, and then you should cut the edge between node y and its parent. So after this operation, a tree will be separate into two parts.
3. Given three integer w, x, y, for the x, y and all nodes between the path from x to y, you should increase their weight by w.
4. Given two integer x, y, you should check the node weights on the path between x and y, and you should output the maximum weight on it.

样例输入:

5
1 2
2 4
2 5
1 3
1 2 3 4 5
6
4 2 3
2 1 2
4 2 3
1 3 5
3 2 1 4
4 1 4

样例输出:

3
-1
7

Hint
We define the illegal situation of different operations: In first operation: if node x and y belong to a same tree, we think it's illegal. In second operation: if x = y or x and y not belong to a same tree, we think it's illegal. In third operation: if x and y not belong to a same tree, we think it's illegal. In fourth operation: if x and y not belong to a same tree, we think it's illegal.

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_C(i, a, b) for (int b____=int(b),i=int(a);i<b____;++i)
#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)
#define DO(n) while(n--)
#define DO_C(n) int n____ = n; while(n____--)

template<class T> 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';}
inline int RD(){ int x; RD(x); return x;}
template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);}
template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);}
template<class T> inline void OT(const T &x){printf("%d\n", x);}
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}

/*--------*/

const int N = 300009, M = 2 * N;

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

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

// private:

inline void Inc(int x, int d){
	if (x == 0) return;
	w0[x] += d, w1[x] += d, delay[x] += d;
}

inline void Release(int x){
	if (x == 0) return;

	if (rev[x]){
		swap(lx, rx);
		rev[lx] ^=1, rev[rx] ^=1;
		rev[x] = 0;
	}

	if (delay[x]){
		Inc(lx, delay[x]), Inc(rx, delay[x]);
		delay[x] = 0;
	}
}

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

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

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

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

	Release(y), Release(x);

	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;
	Update(y);
}

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

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

inline int Root(int x){
	for (x = Access(x); Release(x), lx; x = lx);
	return x;
}

inline void Evert(int x){
	rev[Access(x)] ^= 1;
}

// public:

void Query(int x, int y){
	if (Root(x) != Root(y))
		puts("-1");
	else {
		Access(y); y = 0; do{
			Splay(x), Release(x); if (!p[x]) OT(max(w1[rx], w0[x], w1[y]));
			rt[rx] = true, rt[rx = y] = false, Update(x);
			x = p[y = x];
		} while (x);
	}
}

void Link(int x, int y){
	if (Root(x) == Root(y))
		puts("-1");
	else {
		Evert(x), Splay(x), p[x] = y, Access(x);
	}
}

// Set y as a root, Cut the connection between x and p[x] ..
void Cut(int y, int x){
	if (x == y || Root(x) != Root(y))
		puts("-1");
	else {
		Evert(y), Splay(y), Access(x), Splay(x);
		p[lx] = p[x], rt[lx] = true, p[x] = lx = 0;
	}
}

void Modify(int x, int y, int w){
	if (Root(x) != Root(y))
		puts("-1");
	else {
		Access(y); y = 0; do{
			Splay(x), Release(x); if (!p[x]) Inc(rx, w), w0[x] += w, Inc(y, w);
			rt[rx] = true, rt[rx = y] = false, Update(x);
			x = p[y = x];
		} while (x);
	}
}

#define v b[i]
inline void dfs(int u = 1){
	for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
		p[v] = u, dfs(v);
	}
}

int main(){

	while (scanf("%d", &n) != EOF){
		// Initializing Phase
		FOR_C(i, 2, n << 1){
			RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i];
			nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
			nxt[i] = hd[a[i]], hd[a[i]] = i;
		}

		REP_1(i, n) RD(w0[i]), rt[i] = true;
		p[1] = -1, dfs(), p[1] = 0;

		//Interaction Phase
		int a, b, cmd; DO_C(RD()){
			RD(cmd, a, b); if (cmd == 1) Link(a, b);
			else if (cmd == 2) Cut(a, b);
			else if (cmd == 3) Modify(b, RD(), a);
			else Query(a, b);
		}

		puts("");

		// Rececling ...
		RST(hd, p, l, r, delay, rev);
	}
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。