題目大意:

給定一顆樹(shù),詢(xún)問(wèn)樹(shù)中某個(gè)點(diǎn)x的子樹(shù)中與其距離不超過(guò)d的所有點(diǎn)中本質(zhì)不同的顏色數(shù)
強(qiáng)制在線(xiàn)

題解:

一下午終于把這道題叉掉了。

寫(xiě)了三個(gè)算法,前兩個(gè)都是錯(cuò)的,后一個(gè)是%的網(wǎng)上大爺們的題解.

首先我們發(fā)現(xiàn)這道題有一個(gè)特點(diǎn):沒(méi)有修改操作 !!
這就使我們能夠?qū)︻伾M(jìn)行預(yù)處理。
所以我們可以考慮分別枚舉每個(gè)顏色,對(duì)其去重后更新樹(shù)上的信息。
所以我們可以考慮樹(shù)鏈的并,我們可以對(duì)每種顏色都做一遍樹(shù)鏈的并
容易發(fā)現(xiàn)復(fù)雜度仍然是\(O(nlogn)\)的
但是這樣我們只求出來(lái)的每個(gè)節(jié)點(diǎn)子樹(shù)中不同的顏色的個(gè)數(shù)
并沒(méi)有滿(mǎn)足對(duì)深度的限制
弱弱的我想到這里就繼續(xù)不下去了,不知道下面改怎么寫(xiě),YY了兩個(gè)算法
第一個(gè)算法打著打著感覺(jué)不對(duì),(Ctrl+A) + (Backspace)
第二個(gè)算法打出來(lái)了調(diào)樣例,手模一下發(fā)現(xiàn)算法是錯(cuò)的.(Alt+F4)

---

去%了大爺們的題解:

我們把所有的點(diǎn)按照深度動(dòng)態(tài)地進(jìn)行樹(shù)鏈的并.
這樣,我們就發(fā)現(xiàn)我們實(shí)際上可以求出每一個(gè)深度到樹(shù)根中不同顏色的種類(lèi)
但是我們發(fā)現(xiàn)我們單單考慮了深度的一個(gè)邊界還沒(méi)有結(jié)束.
我們還需要限制深度另一個(gè)邊界和在x子樹(shù)中的限制
我們發(fā)現(xiàn)其實(shí)這兩個(gè)限制等價(jià)于dfs序在x的子樹(shù)dfs序范圍之間.
所以。。。在深度上用線(xiàn)段樹(shù)可持久化即可...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
inline void read(int &x){x=0;char ch;bool flag = false;while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 100010;
struct Edge{int to,next;
}G[maxn<<2];
int head[maxn],cnt;
void add(int u,int v){G[++cnt].to = v;G[cnt].next = head[u];head[u] = cnt;
}
int dfn[maxn],dfs_clock,son[maxn],siz[maxn];
int dep[maxn],top[maxn],fa[maxn],oud[maxn];#define v G[i].to
void dfs(int u){siz[u] = 1;for(int i = head[u];i;i=G[i].next){if(v == fa[u]) continue;fa[v] = u;dep[v] = dep[u] + 1;dfs(v);siz[u] += siz[v];if(siz[son[u]] < siz[v]) son[u] = v;}
}
void dfs(int u,int tp){top[u] = tp;dfn[u] = ++dfs_clock;if(son[u]) dfs(son[u],tp);for(int i = head[u];i;i=G[i].next){if(v == fa[u] || v == son[u]) continue;dfs(v,v);}oud[u] = dfs_clock;
}
#undef v
inline int lca(int u,int v){while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u,v);u = fa[top[u]];}return dep[u] < dep[v] ? u : v;
}
int col[maxn],n;
namespace Trp{struct Node{Node *ch[2];int dfn,siz,fix,id;void update(){siz = ch[0]->siz + ch[1]->siz + 1;}}mem[maxn<<2],*it,*null,*root[maxn];inline void init(){it = mem;null = it++;null->ch[0] = null->ch[1] = 0;null->id = -1;null->dfn = null->siz = 0;}inline Node* newNode(int x,int i){Node *p = it++;p->ch[0] = p->ch[1] = null;p->dfn = x;p->fix = rand();p->siz = 1;p->id = i;return p;}void rotate(Node* &p,int k){Node *y = p->ch[k^1];p->ch[k^1] = y->ch[k];y->ch[k] = p;p->update();y->update();p = y;}void insert(Node* &p,int x,int id){if(p == null) p = newNode(x,id);else{insert(p->ch[p->dfn < x],x,id);p->update();if(p->ch[p->dfn<x]->fix < p->fix)rotate(p,p->dfn > x);}}inline int find(int k,Node *root){Node *p = root;if(k < 1 || k > p->siz) return -1;while(p != null){if(p->ch[0]->siz + 1 == k) return p->id;if(p->ch[0]->siz + 1 > k) p = p->ch[0];else k -= p->ch[0]->siz + 1,p = p->ch[1];}assert(0);}inline int rank(int d,Node* root){int ret = 1;Node *p = root;while(p != null){if(p->dfn < d) ret += p->ch[0]->siz + 1,p = p->ch[1];else p = p->ch[0];}return ret;}
}
namespace seg{struct Node{Node* ch[2];int val;void update(){val = ch[0]->val + ch[1]->val;}}mem[maxn*100],*it,*null,*root[maxn];inline void init(){it = mem;null = it++;null->ch[0] = null->ch[1] = null;null->val = 0;root[0] = null;}Node* insert(Node *rt,int l,int r,int pos,int w){Node *p = it++;*p = *rt;if(l == r){p->val += w;return p;}int mid = l+r >> 1;if(pos <= mid) p->ch[0] = insert(p->ch[0],l,mid,pos,w);else p->ch[1] = insert(p->ch[1],mid+1,r,pos,w);p->update();return p;}int query(Node *p,int l,int r,int L,int R){if(L <= l && r <= R) return p->val;int mid = l+r >> 1;if(R <= mid) return query(p->ch[0],l,mid,L,R);if(L >  mid) return query(p->ch[1],mid+1,r,L,R);return query(p->ch[0],l,mid,L,R) + query(p->ch[1],mid+1,r,L,R);}
}
int q[maxn],l,r,mx;
inline void bfs(){l = 0;r = -1;q[++r] = 1;while(l <= r){int u = q[l++],x = Trp::rank(dfn[u],Trp::root[col[u]]),y,z;mx = max(mx,dep[u]);seg::root[dep[u]] = seg::insert(seg::root[dep[q[l-2]]],1,n,dfn[u],1);Trp::insert(Trp::root[col[u]],dfn[u],u);y = Trp::find(x-1,Trp::root[col[u]]);z = Trp::find(x+1,Trp::root[col[u]]);if(y != -1 && z != -1){int lc = lca(y,z);seg::root[dep[u]] = seg::insert(seg::root[dep[u]],1,n,dfn[lc],1);}if(y != -1){int lc = lca(y,u);seg::root[dep[u]] = seg::insert(seg::root[dep[u]],1,n,dfn[lc],-1);}if(z != -1){int lc = lca(z,u);seg::root[dep[u]] = seg::insert(seg::root[dep[u]],1,n,dfn[lc],-1);}for(int i = head[u];i;i=G[i].next){int v = G[i].to;if(v == fa[u]) continue;q[++r] = v;}}
}
inline void init(){memset(head,0,sizeof head);cnt = 0;memset(son,0,sizeof son);memset(siz,0,sizeof siz);dfs_clock = 0;mx = 0;
}
int main(){int T;read(T);srand(6613);while(T--){init();seg::init();Trp::init();int m;read(n);read(m);for(int i=0;i<=n;++i){Trp::root[i] = Trp::null;seg::root[i] = seg::null;}for(int i=1;i<=n;++i) read(col[i]);for(int i=2;i<=n;++i){read(fa[i]);add(fa[i],i);}dfs(1);dfs(1,1);bfs();int ans = 0;int x,d;while(m--){read(x);read(d);x ^= ans;d ^= ans;int de = dep[x] + d;if(de > mx) de = mx;ans = seg::query(seg::root[de],1,n,dfn[x],oud[x]);printf("%d\n",ans);}}getchar();getchar();return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Skyminer/p/6556815.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 4771: 七彩树 树链的并+可持久化线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。