樹上莫隊也就一句話:
把樹上路徑用歐拉序(入棧出棧序)變成區間,區間莫隊即可
思想就是利用周遊構造出路徑,入棧出棧互相抵消處理多餘的點。
多了細節和讨論:
1.某個點存在一次貢獻為1,存在兩次貢獻為0,
2.莫隊的l,r要通過是否為祖先關系進行讨論
①是祖先關系,棧序是包含的,[in[x],in[y]]
②不是,先出棧的到後入棧的,[out[x],in[y]],LCA因為完全包含x,y是以額外再統計上
3.歐拉序是2*n個點,分塊時候循環到2*n以及數組大小2*N
模闆:
SP10707 COT2 - Count on a tree II
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-YWan5SO1Q2Y5YTMiNGNjNjYhFmN3MzNjZDN3ITN3YDNygDMw8CX4AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.gif)
#include<bits/stdc++.h>
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
namespace Miracle{
const int N=40004;
const int M=100000+5;
int n,m;
struct node{
int nxt,to;
}e[2*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int co[N],b[N];
int a[2*N],tot;
int in[N],out[N];
int fa[N][18];
int dep[N];
void dfs(int x,int d){
dep[x]=d;
in[x]=++tot;a[tot]=x;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa[x][0]) continue;
fa[y][0]=x;
dfs(y,d+1);
}
out[x]=++tot;a[tot]=x;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(reg j=17;j>=0;--j){
if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];
}
if(x==y)return x;
for(reg j=17;j>=0;--j){
if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
}
return fa[x][0];
}
int blo,be[2*N];
struct que{
int l,r,typ;//typ==0 need lca
int lca;
int id;
bool friend operator <(que a,que b){
if(be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
if(be[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
}q[M];
int ans[M];
int l,r;
int buc[N],now;
int vis[N];
void chan(int x,int c){
if(!x) return;
if(c==-1){
if(vis[a[x]]&1) c=-1;
else c=1;
--vis[a[x]];
}else{
if(vis[a[x]]&1) c=-1;
else c=1;
++vis[a[x]];
}
if(c==1){
++buc[co[a[x]]];
if(buc[co[a[x]]]==1) ++now;
}else{
--buc[co[a[x]]];
if(buc[co[a[x]]]==0) --now;
}
}
int lp;
void wrk(){
l=0;r=0;
for(reg i=1;i<=m;++i){
// cout<<"num i "<<i<<" : "<<q[i].l<<" "<<q[i].r<<endl;
while(r<q[i].r) chan(++r,1);
while(l>q[i].l) chan(--l,1);
while(r>q[i].r) chan(r--,-1);
while(l<q[i].l) chan(l++,-1);
// prt(buc,1,lp);
if(q[i].typ==1){
ans[q[i].id]=now;
}else{
// cout<<"lca "<<q[i].lca<<endl;
if(buc[co[q[i].lca]]==0) ans[q[i].id]=now+1;
else ans[q[i].id]=now;
}
}
}
int main(){
rd(n);rd(m);
blo=sqrt(n);
for(reg i=1;i<=n;++i) {
rd(co[i]);
b[i]=co[i];
}
// prt(be,1,n);
sort(b+1,b+n+1);
lp=unique(b+1,b+n+1)-b-1;
for(reg i=1;i<=n;++i){
co[i]=lower_bound(b+1,b+lp+1,co[i])-b;
}
int x,y;
for(reg i=1;i<n;++i){
rd(x);rd(y);add(x,y);add(y,x);
}
dfs(1,1);
for(reg i=1;i<=tot;++i){
be[i]=(i-1)/blo+1;
}
// cout<<tot<<endl;
// prt(be,1,tot);
for(reg j=1;j<=17;++j){
for(reg i=1;i<=n;++i){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
for(reg i=1;i<=m;++i){
rd(x);rd(y);
int anc=lca(x,y);
// cout<<" anc "<<anc<<endl;
if(anc==x||anc==y){
if(in[x]>in[y]) swap(x,y);
q[i].l=in[x];q[i].r=in[y];
q[i].lca=anc;q[i].typ=1;
}else{
if(out[x]>in[y]) swap(x,y);
q[i].l=out[x];q[i].r=in[y];
q[i].lca=anc;q[i].typ=0;
}
q[i].id=i;
}
sort(q+1,q+m+1);
// prt(a,1,tot);
// prt(co,1,n);
wrk();
for(reg i=1;i<=m;++i){
printf("%d\n",ans[i]);
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/3/24 10:43:06
*/
View Code
樹上帶修莫隊?
P4074 [WC2013]糖果公園
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-YWan5SO1Q2Y5YTMiNGNjNjYhFmN3MzNjZDN3ITN3YDNygDMw8CX4AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.gif)
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
template<class T>il void rd(T &x){
char ch;x=0;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');}
template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
namespace Miracle{
const int N=100000+5;
int n,m,qs;
struct node{
int nxt,to;
}e[2*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
int fa[N][19];
int dep[N];
int a[2*N],tot;
int in[N],out[N];
ll w[N],v[N];
int c[N],tmp[N];
void dfs(int x,int d){
dep[x]=d;
a[++tot]=x;in[x]=tot;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa[x][0]) continue;
fa[y][0]=x;
dfs(y,d+1);
}
a[++tot]=x;out[x]=tot;
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(reg j=17;j>=0;--j){
if(dep[fa[x][j]]>=dep[y]) x=fa[x][j];
}
if(x==y) return x;
for(reg j=17;j>=0;--j){
if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
}
return fa[x][0];
}
int be[2*N];
struct que{
int id,l,r,t;
int lca;
bool friend operator <(que a,que b){
if(be[a.l]==be[b.l]){
if(be[a.r]==be[b.r]){
if(be[a.r]&1) return a.t<b.t;
return a.t>b.t;
}
if(be[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
return a.l<b.l;
}
}q[N];
int buc[N];
int vis[N];
ll now;
struct event{
int x,fr,to;
}h[N];
int num1,num2;
ll ans[N];
void upda(int id,int c){
if(c==1){
now+=v[id]*w[buc[id]+1];
}else{
now-=v[id]*w[buc[id]];
}
buc[id]+=c;
}
void chan(int x,int o){
int pos=a[x];
if(vis[pos]&1) upda(c[pos],-1);
else upda(c[pos],1);
vis[pos]+=o;
}
void add(int l,int r,int t){
if(vis[h[t].x]==1){
upda(c[h[t].x],-1);
c[h[t].x]=h[t].to;
upda(c[h[t].x],1);
}
c[h[t].x]=h[t].to;
}
void dele(int l,int r,int t){
if(vis[h[t].x]==1){
upda(c[h[t].x],-1);
c[h[t].x]=h[t].fr;
upda(c[h[t].x],1);
}
c[h[t].x]=h[t].fr;
}
void wrk(){
int l=0,r=0,t=0;
for(reg i=1;i<=num2;++i){
// cout<<" ii "<<i<<" : "<<q[i].id<<" : "<<q[i].l<<" "<<q[i].r<<" tt "<<q[i].t<<endl;
while(t<q[i].t) add(l,r,++t);
while(t>q[i].t) dele(l,r,t--);
while(r<q[i].r) chan(++r,1);
while(l>q[i].l) chan(--l,1);
while(r>q[i].r) chan(r--,-1);
while(l<q[i].l) chan(l++,-1);
if(q[i].lca){
ans[q[i].id]=now+v[c[q[i].lca]]*(w[buc[c[q[i].lca]]+1]);
}else{
ans[q[i].id]=now;
}
}
}
int main(){
rd(n);rd(m);rd(qs);
int blo=pow(qs,0.66666);
for(reg i=1;i<=m;++i) rd(v[i]);
for(reg i=1;i<=n;++i) rd(w[i]);
int x,y;
for(reg i=1;i<n;++i){
rd(x);rd(y);add(x,y);add(y,x);
}
for(reg i=1;i<=n;++i){
rd(c[i]);tmp[i]=c[i];
}
dfs(1,1);
for(reg j=1;j<=17;++j)
for(reg i=1;i<=n;++i){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
for(reg i=1;i<=tot;++i){
be[i]=(i-1)/blo+1;
}
num1=0;
int op;//x,y;//,c;
for(reg i=1;i<=qs;++i){
rd(op);
if(op==0){
++num1;
rd(x);rd(y);
h[num1].x=x;h[num1].to=y;
h[num1].fr=tmp[x];
tmp[x]=y;
}else{
++num2;
rd(x);rd(y);
q[num2].id=num2;
q[num2].t=num1;
int anc=lca(x,y);
if(anc==x||anc==y){
if(in[x]>in[y]) swap(x,y);
q[num2].l=in[x],q[num2].r=in[y];
q[num2].lca=0;
}else{
q[num2].lca=anc;
if(out[x]>in[y]) swap(x,y);
q[num2].l=out[x],q[num2].r=in[y];
}
}
}
sort(q+1,q+num2+1);
wrk();
for(reg i=1;i<=num2;++i){
printf("%lld\n",ans[i]);
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/3/24 12:28:10
*/
可以離線的樹上兩點的查詢也可以用莫隊試試看
單點修改,時限又大的話,帶修莫隊也可以考慮的
進階
1.卡常數:
直接變成序列加加減減的話,可能一個有很多點出現了兩次,先加入再删除,不值得。
可以考慮直接找下一個路徑,把相對的差做出來即可。
這樣,排序還是按照序列排序,直接找路徑顯然常數隻能更優
2.樹上復原莫隊?
有些東西不能支援删除,隻能棧序撤銷
直接放到序列上再用復原莫隊還是要第二次加入的時候處理删除問題的。。。。。
直接在樹上标關鍵點:
設深度是H的倍數,并且子樹大小大于H的(防止被掃帚卡)設為關鍵點
關鍵點有n/H個
每個點距離最近的祖先關鍵點距離不超過2*H
每個詢問放在第一個祖先的關鍵點上(x,y取較近的那一個)
每個關鍵點的詢問:一路dfs,到了一個詢問(x,y),這個時候dfs到了y,就直接找到較近的x,然後再從x退到關鍵點
複雜度:O(mH+(n/H)*n)
H=n/sqrt(m)時候最優
upda:2019.7.3
這個復原莫隊還要考慮一些特殊情況:
1.x,y詢問挂的位置z應當使得x、y一個位于z子樹,一個位于z的子樹外。
2.如果不能達成1,那麼這個詢問一定距離<=2*H暴力即可。