HDU 4916 Count on the path
題意：
給定一棵樹和m個詢問 每個詢問要求回答不在u和v兩節點所形成的路徑上的點的最小標號
思路：
一開始以為是LCA… 不過T了好幾次… 後來發現不用LCA也可做
考慮每個詢問u和v 如果他們的lca不是1 則1一定是答案 不過求lca會T 那麼我們只需要在遍歷樹的時候給節點染色 染的顏色就是1的兒子的顏色 如果x這個點在y的子樹中（y是1的兒子）那麼他的顏色就是y
染完色後我們考慮答案是如何構成的
如圖所示 答案即是 紅色 藍色 綠色的子樹中節點的最小值 那麼我們只需要分開三部分求解即可<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tqjS5WZbdV1beF2x7cq+0tR1zqq4+bXE19PK99bQtdp4tPO1xL3ateOx6rrFICDV4rj2v8nS1M2ouf3K99DOZHDH873iICDT0MHL1eK49r7Nv8nS1L3ivvbCzMmrus267MmrtcSyv7fWPC9wPgo8cD62qNLlZ1t1XbHtyr51vdq148nPw+a1vTG1xMK3vrbW0MXUsuC1xNfTyve1xNfu0KG92rXjseq6xSAgvLTNvNbQwLbJq7K/t9YgINKyv8nS1MD708Nm1/bK99DOZHDH873iPC9wPgo8cD48YnI+CjwvcD4KPHA+16LS4qO6PC9wPgo8cD7M4sS/1tCyu8jDwLbJq7K/t9aw/LqswszJq7K/t9YgINKysruw0cLMyauyv7fWt8XU2rrsyauyv7fW1tC/vMLHtcTUrdLyvs3Kx3W6zXa92rXj1tC1xNK7uPa/ycTcyscxPC9wPgo8cD7TydPaztLQtLXEysdkZnMgILq8tee74bGs1bsgIMv50tS8x7XDvNPVuyAgsqLTw0MmIzQzOyYjNDM7zOG9uzwvcD4KPHA+PGJyPgo8L3A+CjxwPrT6wuujujwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
using namespace std;
#define N 1000010
int f[N][4], g[N], col[N], head[N];
int n, m, color, tot, ans;
struct edge {
int v, next;
} ed[N * 2];
int d(int a, int b) {
if (a < b)
return a;
return b;
}
void add(int u, int v) {
ed[tot].v = v;
ed[tot].next = head[u];
head[u] = tot++;
}
void dfs1(int u, int fa) {
int i, v;
if (u != 1)
col[u] = color;
for (i = head[u]; ~i; i = ed[i].next) {
v = ed[i].v;
if (u == 1)
color = v;
if (v != fa) {
dfs1(v, u);
f[u][3] = d(v, f[v][0]);
sort(f[u], f[u] + 4);
}
}
}
void dfs2(int u, int fa) {
if (fa != 1) {
if (d(u, f[u][0]) != f[fa][0])
g[u] = f[fa][0];
else
g[u] = f[fa][1];
if (g[u] > g[fa])
g[u] = g[fa];
}
int i, v;
for (i = head[u]; ~i; i = ed[i].next) {
v = ed[i].v;
if (v != fa)
dfs2(v, u);
}
}
int main() {
int i, j, u, v;
while (~scanf("%d%d", &n, &m)) {
for (i = 1; i <= n; i++) {
f[i][0] = f[i][1] = f[i][2] = f[i][3] = g[i] = N;
head[i] = -1;
}
col[1] = 1;
tot = ans = 0;
for (i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs1(1, 1);
dfs2(1, 1);
for (i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
u ^= ans;
v ^= ans;
if (col[u] == col[v]) {
if (u == 1 || v == 1)
ans = 2;
else
ans = 1;
} else {
if (u > v)
swap(u, v);
ans = min(f[v][0], min(g[u], g[v]));
if (u != 1) {
ans = min(ans, f[u][0]);
v = min(col[v], f[col[v]][0]);
u = min(col[u], f[col[u]][0]);
for (j = 0; j < 3; j++) {
if (f[1][j] != u && f[1][j] != v) {
ans = min(ans, f[1][j]);
break;
}
}
} else {
v = min(col[v], f[col[v]][0]);
for (j = 0; j < 3; j++) {
if (f[1][j] != v) {
ans = min(ans, f[1][j]);
break;
}
}
}
}
printf("%d\n", ans);
}
}
return 0;
}
