題目大意:給出一棵樹,問任意兩點之間有多少種不同的顔色,一個人可能會有色盲,會将A和B當成一種顔色。
思路:比較裸的樹上莫隊,寫出來之後,很慢,懷疑是分塊的緣故,然後果斷找了當年比賽的标稱交上去,瞬間rk1,大概看了一眼,他好像是直接用DFS序+曼哈頓距離最小生成樹搞的,為什麼會比分塊快?
昨天下午看到這個題之後就一直在研究樹上莫隊的正确姿勢,然後先寫了樹分塊,後來看了很多牛人的SPOJ COT2的題解,後來又和同學探讨了好久才弄明白。
首先先将樹分塊,然後把區間排序,按照第一權值為左端點所在塊的編号,右端點在DFS序中的位置排序,關鍵是轉移。有一種vfk的靠譜一點的方法。對于任意一個狀态,在樹上表示[l,r]的路徑,目前的狀态隻存{x|x∈[l,r],x != LCA(l,r)}這些點的顔色,這樣就大概有兩種情況,一種是兩條鍊,沒有中間的LCA,或者是一條鍊,沒有頂端的LCA。然後一直這樣轉移,例如從[l,r]轉移到[x,y]的時候,我們隻需要暴力從l->x,y->r,注意記錄一個标記數組,在轉移的時候把路徑上的所有點取反。這樣轉移之後還是{x|x∈[l,r],x != LCA(l,r)}這些點。統計答案的時候将LCA加回來,然後再删掉。
注意:找LCA要倍增!千萬别像我以為寫不寫倍增都是O(n)然後T一晚上。。。
CODE:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100100
using namespace std;
inline char GetChar()
{
static const int L = (1 << 15);
static char buffer[L],*S = buffer,*T = buffer;
if(S == T) {
T = (S = buffer) + fread(buffer,1,L,stdin);
if(S == T) return EOF;
}
return *S++;
}
inline int GetInt()
{
int c;
while(!isdigit(c = GetChar()));
int x = c - '0';
while(isdigit(c = GetChar()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
int block_size,belong[MAX],blocks;
int pos[MAX],cnt;
int size[MAX],root;
struct Ask{
int x,y,_id;
int mixed,_mixed;
bool operator <(const Ask &a)const {
if(belong[x] == belong[a.x]) return pos[y] < pos[a.y];
return belong[x] < belong[a.x];
}
void Read(int p) {
x = GetInt(),y = GetInt();
mixed = GetInt(),_mixed = GetInt();
if(pos[x] > pos[y]) swap(x,y);
_id = p;
}
}ask[MAX << 1];
int points,asks;
int head[MAX],total;
int _next[MAX << 1],aim[MAX << 1];
int deep[MAX],father[MAX][20];
int src[MAX];
int num[MAX],colors;
bool v[MAX];
int ans[MAX];
inline void Add(int x,int y)
{
_next[++total] = head[x];
aim[total] = y;
head[x] = total;
}
void DFS(int x,int last)
{
father[x][0] = last;
pos[x] = ++cnt;
deep[x] = deep[last] + 1;
for(int i = head[x]; i; i = _next[i]) {
if(aim[i] == last) continue;
if(size[belong[x]] < block_size)
++size[belong[x]],belong[aim[i]] = belong[x];
else ++size[++blocks],belong[aim[i]] = blocks;
DFS(aim[i],x);
}
}
inline void Change(int x,int c)
{
if(!num[x]) ++num[x],++colors;
else if(num[x] == 1 && c == -1) --num[x],--colors;
else num[x] += c;
}
inline int GetLCA(int x,int y)
{
if(deep[x] < deep[y]) swap(x,y);
for(int i = 19; ~i; --i)
if(deep[father[x][i]] >= deep[y])
x = father[x][i];
if(x == y) return x;
for(int i = 19; ~i; --i)
if(father[x][i] != father[y][i])
x = father[x][i],y = father[y][i];
return father[x][0];
}
inline void Work(int x,int y,int lca)
{
for(; x != lca; x = father[x][0]) {
Change(src[x],v[x] ? -1:1);
v[x] ^= 1;
}
for(; y != lca; y = father[y][0]) {
Change(src[y],v[y] ? -1:1);
v[y] ^= 1;
}
}
inline void Solve(int p)
{
static int l = root,r = root,lca;
Work(l,ask[p].x,GetLCA(l,ask[p].x));
Work(r,ask[p].y,GetLCA(r,ask[p].y));
l = ask[p].x,r = ask[p].y;
lca = GetLCA(l,r);
Change(src[lca],1);
ans[ask[p]._id] = colors;
if(ask[p].mixed != ask[p]._mixed)
ans[ask[p]._id] -= num[ask[p].mixed] && num[ask[p]._mixed];
Change(src[lca],-1);
}
inline void SparseTable()
{
for(int j = 1; j < 20; ++j)
for(int i = 1; i <= points; ++i)
father[i][j] = father[father[i][j - 1]][j - 1];
}
int main()
{
//freopen("apple.in","r",stdin);
//freopen("apple.out","w",stdout);
cin >> points >> asks;
for(int i = 1; i <= points; ++i)
src[i] = GetInt();
for(int x,y,i = 1; i <= points; ++i) {
x = GetInt(),y = GetInt();
Add(x,y),Add(y,x);
}
block_size = sqrt(points + 1);
size[1] = 1;
belong[0] = 1;
blocks = 1;
DFS(0,MAX - 1);
root = aim[head[0]];
SparseTable();
for(int i = 1; i <= asks; ++i)
ask[i].Read(i);
sort(ask + 1,ask + asks + 1);
for(int i = 1; i <= asks; ++i)
Solve(i);
for(int i = 1; i <= asks; ++i)
printf("%d\n",ans[i]);
return 0;
}