[bzoj] 3757: 苹果树 发表于 Mar 26 2015 | 分类于 bzoj | 题意一棵树上每个节点都有颜色,每次回答树链上有几种颜色,有时询问视两种颜色为同一种颜色 传送门 分析莫队算法 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147#include <cstdio>#define Rep(i,l,r) for(i=(l);i<=(r);i++)#define Rev(i,r,l) for(i=(r);i>=(l);i--)int CH , NEG ;template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ;}template <typename TP>inline void reads(TP& ret) {truewhile (ret=getchar() , ret<'!') ;truewhile (CH=getchar() , CH>'!') ;}#include <algorithm>#include <cmath>#define maxn 50010LL#define maxm 50010LL#define maxq 100010LL#define maxk 17LLstruct FST { int to , next ; } e[maxm<<1] ;int star[maxn] = {0} , tote = 1 ;void AddEdge(int u , int v) { e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ; }int n , m , root , ansnow ;int cntblc , szblc , idx , top ;int col[maxn] , cnt[maxn] = {0} ;int dfn[maxn] , sta[maxn] , belong[maxn] , dep[maxn] , size[maxn] , par[maxn][maxk] ;int ans[maxq] ;bool vis[maxn] = {0} ;struct QUERY {trueint u , v , a , b , id ;truebool operator < (const QUERY& b) consttrue{ return belong[u]==belong[b.u]? dfn[v]<dfn[b.v] : belong[u]<belong[b.u] ; }} q[maxq] ;void dfs(int u , int fa) {int v , p ;truesta[++top] = u ;truepar[u][0] = fa ;truedfn[u] = ++idx ;truedep[u] = dep[fa]+1 ;truesize[u] = 0 ;truefor (p = star[u] ; p ; p = e[p].next)truetrueif (v=e[p].to , v!=fa) {truetruetruedfs(v , u) ;truetruetruesize[u] += size[v] ;truetruetrueif (size[u] >= szblc) {truetruetruetruesize[u] = 0 ;truetruetruetruecntblc ++ ;truetruetruetruewhile (sta[top] != u) belong[sta[top--]] = cntblc ;truetruetrue}truetrue}truesize[u] ++ ;}void ST() {int i , k ;trueRep (k,1,maxk-1)truetrueRep (i,1,n)truetruetruepar[i][k] = par[par[i][k-1]][k-1] ;}int LCA(int u , int v) {trueint k ;trueif (dep[u] < dep[v]) std::swap(u,v) ;trueRev (k,maxk-1,0)truetrueif (dep[par[u][k]] >= dep[v]) u = par[u][k] ;trueif (u == v) return u ;trueRev (k,maxk-1,0)truetrueif (par[u][k] != par[v][k])truetruetrueu = par[u][k] , v = par[v][k] ;truereturn par[u][0] ;}void Reverse(int u) {trueif (!vis[u]) { vis[u]=true;cnt[col[u]]++;if(cnt[col[u]]==1)ansnow++; }trueelse { vis[u]=false;cnt[col[u]]--;if(cnt[col[u]]==0)ansnow--; }}void MoveTo(int u,int v) {truewhile (u != v)truetrueif (dep[u] > dep[v]) Reverse(u) , u = par[u][0] ;truetrueelse Reverse(v) , v = par[v][0] ;}void GetAns(int i , int lca) {trueReverse(lca) ;trueans[q[i].id] = ansnow ;trueif (q[i].a!=q[i].b && cnt[q[i].a] && cnt[q[i].b]) ans[q[i].id] -- ;trueReverse(lca) ;}int main() {int i , u , v , lca ;// #define READtrue#ifdef READtruetruefreopen(".in" ,"r",stdin ) ;truetruefreopen(".out","w",stdout) ;true#endiftrueread(n) , read(m) ;trueif (n < 5) szblc = n ;trueelse szblc = (int)pow(n,2.0/3.0) ;trueRep (i,1,n) read(col[i]) ;trueRep (i,1,n) {truetrueread(u) , read(v) ;truetrueif (!u) root = v ;truetrueelse if (!v) root = u ;truetrueelse AddEdge(u,v) , AddEdge(v,u) ;true}truecntblc = idx = dep[0] = ansnow = top = 0 ;truedfs(root,0) ;truecntblc ++ ;truewhile (top) belong[sta[top--]] = cntblc ;trueST() ;trueRep (i,1,m) {truetrueread(u) , read(v) ;truetrueif (belong[u] > belong[v]) std::swap(u,v) ;truetrueq[i].u = u , q[i].v= v ;truetrueread(q[i].a) , read(q[i].b) ;truetrueq[i].id = i ;true}truestd::sort(q+1,q+m+1) ;truelca = LCA(q[1].u,q[1].v) ;trueMoveTo(q[1].u,q[1].v) ;trueGetAns(1,lca) ;trueRep (i,2,m) {truetrueMoveTo(q[i-1].u,q[i].u) ;truetrueMoveTo(q[i-1].v,q[i].v) ;truetruelca = LCA(q[i].u,q[i].v) ;truetrueGetAns(i,lca) ;true}trueRep (i,1,m) printf("%d\n", ans[i]) ;true#ifdef READtruetruefclose(stdin) ; fclose(stdout) ;true#elsetruetruegetchar() ; getchar() ;true#endiftruereturn 0 ;}