首先，我們求出樹的重鏈，然后對于每一條鏈，建一顆線段樹
樹大概長這樣：
（其中用紅邊連起來的是一條條重鏈）
在線段樹上，我們維護：
Opt(u)：經過 u節點代表的鏈的其中一段 的兩個白點間的最長路徑長度
MaxL(u)：u節點代表的鏈的左端點到最遠的白點的距離
MaxR(u)：u節點代表的鏈的右端點到最遠的白點的距離
怎么維護呢？
我們再定義一些輔助變量方便描述：
D(i)：節點i到最遠的白點的距離
D2(i)：節點i到次遠的白點的距離
Dist(x,y)：節點x,y之間的距離
Lc：線段樹上左兒子
Rc：線段樹上右兒子
當 l==r 即鏈只有一個節點時：
若u為黑色：
MaxL(u)=MaxR(u)=D(L)
Opt(u)=D(L)+D2(L)
若u為白色：
MaxL(u)=MaxR(u)=Max{D(L),0}
Opt(u)=Max{D(L)+D2(L),D(L)}
然后考慮如何push_up：
MaxL(u)=Max{MaxL(Lc),Dist(L,mid+1)+MaxL(Rc)}
MaxR(u)=Max{MaxR(Rc),Dist(mid,R)+MaxR(Lc)}
Opt(u)=Max{Opt(Lc),Opt(Rc),MaxR(Lc)+MaxL(Rc)+Dist(mid,mid+1)}
這樣我們就維護好線段樹啦，接下來考慮怎么在樹上修改一個點的顏色：
假設我們要修改黃色點的顏色，那么我們肯定要修改被黃色筆框住的這條鏈
然后藍色點肯定也被影響了，所以我們接下來修改被藍色筆框住的這條鏈
再接下來綠色點也被影響力，所以我們修改被綠色筆框住的這條鏈
而下面已經沒有點被影響了，修改結束
可見要修改一個點，我們只需要一層層鏈跳上去直到當前的鏈頭無父節點為止
然后，我們還要考慮一下如何維護D(i)和D2(i) (節點到最遠和次遠白點的距離)：
對此，我們對每個點維護一個大根堆，記錄這個點到每個白點的距離
D(i)=s.top();
s.pop();
D2(i)=s.top();
s.push(D(i));
這樣就可以求出D(i)和D2(i)啦
最后，在全局用個堆維護每條鏈的Opt，就可以直接查詢了
這是Query on a tree IV的代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std
;
const int maxn
=100005;
const int inf
=1e9;
struct work
{priority_queue
<int> f
,g
;inline void ins(int v
) { if(v
!= -inf
) f
.push(v
); } inline void era(int v
) { if(v
!= -inf
) g
.push(v
); }inline int top() {while(1){if(f
.empty()) return -inf
;if(g
.empty()) return f
.top();if(f
.top() == g
.top()) f
.pop(), g
.pop();else return f
.top();}}
}h
[maxn
], ans
;
struct Edge
{int u
,v
,w
,next
;
}edge
[maxn
<<1];
struct seg
{int l
,r
,v
,ls
,rs
;
}st
[maxn
<<2];
int wn
,n
,m
,head
[maxn
],cnt
,col
[maxn
],rt
[maxn
],onp
;
int sz
[maxn
],fa
[maxn
],dep
[maxn
],son
[maxn
];
int tid
[maxn
],ord
[maxn
],ind
,top
[maxn
],len
[maxn
];
inline int read() {int p
=0,w
=1; char ch
=getchar();while(ch
>'9'||ch
<'0') {if(ch
=='-') w
= -1; ch
=getchar();}while(ch
>='0'&&ch
<='9') p
=p
*10+ch
-'0',ch
=getchar();return p
*w
;
}
void add(int u
,int v
,int w
){edge
[cnt
].u
=u
;edge
[cnt
].v
=v
;edge
[cnt
].w
=w
;edge
[cnt
].next
=head
[u
];head
[u
]=cnt
++;
}
#define dis(x) dep[ord[x]]
void push(int u
,int l
,int r
){int ls
=st
[u
].ls
,rs
=st
[u
].rs
,mid
=(l
+r
)>>1;st
[u
].l
=max(st
[ls
].l
,st
[rs
].l
+dis(mid
+1)-dis(l
));st
[u
].r
=max(st
[rs
].r
,st
[ls
].r
+dis(r
)-dis(mid
));st
[u
].v
=max(max(st
[ls
].v
,st
[rs
].v
),st
[ls
].r
+st
[rs
].l
+dis(mid
+1)-dis(mid
));
}
void build(int &u
,int l
,int r
){if(!u
) u
=++onp
;if(l
==r
){int x
=ord
[l
];for(int i
=head
[x
];i
!=-1;i
=edge
[i
].next
){int v
=edge
[i
].v
;if(v
==fa
[x
]||v
==son
[x
]) continue;h
[x
].ins(st
[rt
[v
]].l
+dep
[v
]-dep
[x
]);}int d1
=h
[x
].top(); h
[x
].era(d1
); int d2
=h
[x
].top(); h
[x
].ins(d1
);st
[u
].l
=st
[u
].r
=max(d1
,0); st
[u
].v
=max(0,max(d1
,d1
+d2
));return;}int mid
=(l
+r
)>>1;build(st
[u
].ls
,l
,mid
);build(st
[u
].rs
,mid
+1,r
);push(u
,l
,r
);
}
void update(int u
,int l
,int r
,int v
,int s
){if(l
==r
){if(v
==s
){int d1
=h
[v
].top();h
[v
].era(d1
); int d2
= h
[v
].top(); h
[v
].ins(d1
);if(col
[v
]) st
[u
].l
=st
[u
].r
=d1
,st
[u
].v
=d1
+d2
;else st
[u
].l
=st
[u
].r
=max(d1
,0),st
[u
].v
=max(0,max(d1
,d1
+d2
));}else{h
[v
].ins(st
[rt
[s
]].l
+dep
[s
]-dep
[v
]);int d1
= h
[v
].top(); h
[v
].era(d1
);int d2
= h
[v
].top(); h
[v
].ins(d1
);if(col
[v
]) st
[u
].l
=st
[u
].r
=d1
,st
[u
].v
=d1
+d2
;else st
[u
].l
=st
[u
].r
=max(d1
,0),st
[u
].v
=max(0,max(d1
,d1
+d2
));}return;}int mid
=(l
+r
)>>1;if(tid
[v
]<=mid
) update(st
[u
].ls
,l
,mid
,v
,s
);else update(st
[u
].rs
,mid
+1,r
,v
,s
);push(u
,l
,r
);
}
void dfs1(int u
){sz
[u
]=1;for(int i
=head
[u
];i
!=-1;i
=edge
[i
].next
){int v
=edge
[i
].v
;int w
=edge
[i
].w
;if(v
==fa
[u
]) continue;fa
[v
]=u
; dep
[v
]=dep
[u
]+w
;dfs1(v
);sz
[u
]+=sz
[v
];if(sz
[v
]>sz
[son
[u
]]) son
[u
]=v
;}
}
void dfs2(int u
,int tp
){tid
[u
]=++ind
;top
[u
]=tp
;ord
[ind
]=u
;len
[tp
]++;if(!son
[u
]) return;dfs2(son
[u
],tp
);for(int i
=head
[u
];i
!=-1;i
=edge
[i
].next
){int v
=edge
[i
].v
;if(v
==fa
[u
]||v
==son
[u
]) continue;dfs2(v
,v
);}
}
int main(){ios
::sync_with_stdio(false);memset(head
,-1,sizeof(head
));wn
=n
=read();int u
,v
,w
;for(int i
=1;i
<n
;i
++){u
=read();v
=read();w
=read();add(u
,v
,w
);add(v
,u
,w
);}dfs1(1);dfs2(1,1);ans
.ins(0);for(int i
=n
;i
;i
--){int u
=ord
[i
]; if(u
!=top
[u
]) continue; build(rt
[u
],tid
[u
],tid
[u
]+len
[u
]-1); ans
.ins(st
[rt
[u
]].v
);}m
=read();char ch
;for(int i
=1;i
<=m
;i
++){ch
=getchar();while(ch
!='C'&&ch
!='A') ch
=getchar();if(ch
=='C'){int x
=read(); col
[x
]^= 1;if(col
[x
]==0) wn
++; else wn
--;for(int u
=x
,p
=u
;u
;u
=fa
[u
]){int tp
=top
[u
];int p1
=st
[rt
[tp
]].v
,d1
=st
[rt
[tp
]].l
;if(fa
[tp
]) h
[fa
[tp
]].era(st
[rt
[tp
]].l
+dep
[tp
]-dep
[fa
[tp
]]);update(rt
[tp
],tid
[tp
],tid
[tp
]+len
[tp
]-1,u
,p
);int p2
=st
[rt
[tp
]].v
,d2
=st
[rt
[tp
]].l
;if(p1
!=p2
) ans
.era(p1
),ans
.ins(p2
);p
=u
=tp
;}}else {if(wn
==0) printf("They have disappeared.\n");else printf("%d\n", ans
.top());}}return 0;
}
捉迷藏的代碼只需要改一下輸入輸出，就不貼了
總結
以上是生活随笔為你收集整理的[BZOJ1095][ZJOI2007]捉迷藏 Query on a tree IV（树链剖分）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
