首页 > ACM题库 > HDU-杭电 > hdu 3216 Graph of Black and White待解决[解题报告]C++
2014
03-07

hdu 3216 Graph of Black and White待解决[解题报告]C++

Graph of Black and White

问题描述 :

Once upon a time, there was a graph. Actually, it was an undirected forest, i.e., an undirected graph without circles. There were N nodes in this forest, numbered from 1 to N inclusively, with each node colored black or white. Elves had been living in the forest for many years. Their homes were inside the nodes, and sometimes they would move their homes or visit other elves living in another node. However, they could only move between nodes that were connected by an edge or a path formed by several end-to-end connected edges. In other words, they could only move in the same tree. If two nodes were not connected, the elves could not travel between them. When they were passing a node, including the starting and the ending ones, they should use black or white magic power according to the color of the node. Waste is criminal, so during a journey the elves never pass a node twice.

The structure of the forest might change, when no elves were travelling. Two disconnected nodes might be connected by a new edge between them, or an existing edge might disappear, or the color of a node might change. Anyway, there would never be circles in the forest, so the forest remained a forest. THUS HARMONY LONG LASTS!

Elves were intelligent. They knew everything happening in the forest. And they knew how much black and white magic power was used when they travel. Why? Because YY, the most intelligent one elf, simulated everything and told them.

输入:

Input contains several test cases.

For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.

The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.

M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:

add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.

del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.

set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).

query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.

Input ends with N=M=0.

输出:

Input contains several test cases.

For each test case, the first line contains two positive integers, N (N ≤ 10000) and M (M ≤ 100000), indicating the number of nodes in the graph and the number of operations that YY should simulate. At the beginning of his simulation, there were not any edge in the forest.

The following lines contains N space separated characters, each being ‘B’ or ‘W’ (quotes for clarity), the ith of which indicates the color of the node numbered i, black or white.

M lines follow, indicating the M operations to simulate. For each line, it will be one of the four types:

add u v
The two nodes numbered u and v (1≤u, v≤N, and u≠v) are connected by a new edge. It is guaranteed that these two nodes are not connected before this operation.

del u v
The edge between the two nodes numbered u and v (1≤u, v≤N, and u≠v) disappears. It is guaranteed that this edge exists before this operation.

set u c
The color of the node numbered u (1≤u≤N) is set to c (c=’B’ or ‘W’, quotes for clarity).

query u v
Now YY tells the elves the number of black and white nodes that have to be passed when travelling between nodes numbered u and v (1≤u, v≤N) inclusively, or tells them the journey is impossible.

Input ends with N=M=0.

样例输入:

3 8
B W B
query 1 2
add 1 2
add 2 3
query 1 3
del 2 3
add 1 3
set 1 W
query 3 2
0 0

样例输出:

-1
2 1
1 2


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。