題目鏈接

(BZOJ) https://www.lydsy.com/JudgeOnline/problem.php?id=4732
(UOJ) http://uoj.ac/problem/268

題解

首先考慮，給定一條路徑，如何計算與其相交的所有路徑的權值和？顯然一條路徑和另一條路徑相交，當且僅當這條路徑的LCA在另一條路徑上，或者另一條路徑的LCA在這條路徑上。那么我們考慮維護兩個數組\(a\)和\(b\), 分別表示以某點為LCA的路徑權值和以及覆蓋這個點但不以該點為LCA的路徑權值和，則路徑\((u,v)\)的價值為\(\sum_{p \in (u,v)}b_p+a_{LCA(u,v)}\).
下面我們要求路徑的最大權值，考慮鏈分治。在一條重鏈上統計LCA在這條重鏈上的鏈的答案。假設一條鏈和該重鏈相交的部分為\((u,v)\)其中\(u\)是\(v\)的祖先也是鏈的LCA。若\(u\ne v\), 該鏈的權值為\(h_u+h_v+\sum^v_{i=u}a_i+b_u\)，否則為\(h_u+h'_u+a_u+b_u\), 其中\(h_u\)和\(h'_u\)分別為\(u\)點的輕兒子引出的鏈的\(\sum a_i\)的最大值和次大值。一條重鏈的權值等于上面的式子在\(u\)和\(v\)變化時的最大值，考慮維護這個最大值，對于\(u\ne v\)的情況，需要采取最大子段和的維護方式；對于\(u=v\)的情況，就是簡單的區間修改區間最大值，都可以用線段樹維護。總答案等于所有重鏈的權值最大值，因此我們開一個multiset維護所有重鏈的權值。
考慮修改。修改時我們需要把一條鏈上的\(b\)增加一個權值\(w\)(可能是負數)，再把LCA處的\(a\)增加一個權值\(w\). 修改\(b\)在重鏈上是區間修改，這個可以簡單地進行打標記，把后綴和和最大子段和加上某一個值。修改\(a\)在重鏈上是單點修改。但是一個\(a\)的修改還會影響到它所在重鏈頂端的父親的\(h\), 那個點的\(h\)改變又會影響它所在重鏈頂端的父親的\(h\)……直到根，因此需要不斷跳重鏈修改。這條鏈的\(\sum a_i\)最大值就相當于我們在線段樹中維護的“最大前綴和”那個量(\(\sum^v_{i=u}a_i+h_v\)), 因此可以直接重新查出，設為\(sa_i\). 為了快速維護\(sa\)的最大次大，我們只需對每個點再開一個multiset記錄一下即可。每次對一條鏈進行修改后，需要重新計算這條鏈的權值，更新總答案multiset.
時間復雜度\(O(n\log^2n)\).
注意multiset用兩個堆實現會快，線段樹給每條鏈開一棵比\([1,n]\)開一棵要快。

代碼

人丑常數大……

#include<bits/stdc++.h> #define llong long long using namespace std;inline int read() {int w=1,s=0;char ch=getchar();while(!isdigit(ch)) {if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)) {s=s*10+ch-'0';ch=getchar();}return w*s; }const int N = 1e5; struct Edge {int nxt,v; } e[(N<<1)+3]; struct Query {int u,v,w; } qr[N+3]; int fe[N+3]; int fa[N+3]; int dfn[N+3],idfn[N+3]; int dep[N+3]; int sz[N+3]; int hvs[N+3]; int tpn[N+3],btn[N+3]; llong a[N+3],h[N+3],h2[N+3],hv[N+3],sa[N+3]; int n,q,en,dfnn;struct Multiset {priority_queue<llong> q1,q2;void insert(llong x) {q1.push(x);}void erase(llong x) {q2.push(x);}llong getmx(){while(!q2.empty()&&q1.top()==q2.top()) {q1.pop(),q2.pop();}return q1.top();}llong getmx2(){llong mx = getmx(); erase(mx); llong ret = getmx(); insert(mx); return ret;} }; Multiset lt[N+3]; int ltn[N+3]; Multiset s;void addedge(int u,int v) {en++; e[en].v = v;e[en].nxt = fe[u]; fe[u] = en; }void dfs1(int u) {sz[u] = 1; hvs[u] = 0;for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==fa[u]) continue;fa[v] = u;dep[v] = dep[u]+1;dfs1(v);sz[u] += sz[v];if(hvs[u]==0||sz[v]>sz[hvs[u]]) {hvs[u] = v;}} } void dfs2(int u) {dfn[u] = ++dfnn; idfn[dfnn] = u;if(!hvs[u]) {btn[u] = u; s.insert(0ll); return;}tpn[hvs[u]] = tpn[u]; dfs2(hvs[u]); btn[u] = btn[hvs[u]];for(int i=fe[u]; i; i=e[i].nxt){int v = e[i].v;if(v==fa[u]||v==hvs[u]) continue;lt[u].insert(0); ltn[u]++;tpn[v] = v;dfs2(v);} }struct Data {llong v,lv,rv,lrv;Data() {v = lv = rv = lrv = 0ll;}Data(llong _v,llong _lv,llong _rv,llong _lrv):v(_v),lv(_lv),rv(_rv),lrv(_lrv) {} }; Data operator +(const Data &x,const Data &y) {Data ret;ret.lrv = x.lrv+y.lrv;ret.lv = max(x.lv,x.lrv+y.lv);ret.rv = max(y.rv,x.rv+y.lrv);ret.v = max(max(x.v,y.v),x.rv+y.lv);return ret; } struct SegmentTree {struct SgTNode{Data x; llong tag;} sgt[(N<<2)+3];void maketag(int u,llong tag){sgt[u].x.rv += tag; sgt[u].x.v += tag;sgt[u].tag += tag;}void pushdown(int u){llong tag = sgt[u].tag;if(tag){maketag(u<<1,tag); maketag(u<<1|1,tag);sgt[u].tag = 0ll;}}void upd(int u,int le,int ri,int pos){if(le==ri) {int pos0 = idfn[pos]; sgt[u].x = Data(a[pos0]+sgt[u].tag+h[pos0],a[pos0]+h[pos0],a[pos0]+sgt[u].tag+h[pos0],a[pos0]); return;}pushdown(u);int mid = (le+ri)>>1;if(pos<=mid) upd(u<<1,le,mid,pos);else upd(u<<1|1,mid+1,ri,pos);sgt[u].x = sgt[u<<1].x+sgt[u<<1|1].x;}void addb(int u,int le,int ri,int lb,int rb,llong x){if(le>=lb && ri<=rb) {maketag(u,x); return;}pushdown(u);int mid = (le+ri)>>1;if(lb<=mid) addb(u<<1,le,mid,lb,rb,x);if(rb>mid) addb(u<<1|1,mid+1,ri,lb,rb,x);sgt[u].x = sgt[u<<1].x+sgt[u<<1|1].x;}Data query(int u,int le,int ri,int lb,int rb){if(le>=lb && ri<=rb) {return sgt[u].x;}pushdown(u);int mid = (le+ri)>>1; Data ret;if(rb<=mid) ret = query(u<<1,le,mid,lb,rb);else if(lb>mid) ret = query(u<<1|1,mid+1,ri,lb,rb);else ret = query(u<<1,le,mid,lb,rb)+query(u<<1|1,mid+1,ri,lb,rb);sgt[u].x = sgt[u<<1].x+sgt[u<<1|1].x;return ret;} } sgt; struct SegmentTree2 {struct SgTNode{llong tag,mx;} sgt[(N<<2)+3];void maketag(int u,llong tag){sgt[u].mx += tag; sgt[u].tag += tag;}void pushdown(int u){llong tag = sgt[u].tag;if(tag){maketag(u<<1,tag); maketag(u<<1|1,tag);sgt[u].tag = 0;}}void add(int u,int le,int ri,int lb,int rb,llong x){if(le>=lb && ri<=rb) {maketag(u,x); return;}pushdown(u);int mid = (le+ri)>>1;if(lb<=mid) add(u<<1,le,mid,lb,rb,x);if(rb>mid) add(u<<1|1,mid+1,ri,lb,rb,x);sgt[u].mx = max(sgt[u<<1].mx,sgt[u<<1|1].mx);}llong query(int u,int le,int ri,int lb,int rb){if(le>=lb && ri<=rb) {return sgt[u].mx;}pushdown(u);int mid = (le+ri)>>1; llong ret = 0ll;if(lb<=mid) ret = max(ret,query(u<<1,le,mid,lb,rb));if(rb>mid) ret = max(ret,query(u<<1|1,mid+1,ri,lb,rb));sgt[u].mx = max(sgt[u<<1].mx,sgt[u<<1|1].mx);return ret;} } sgt2;void calcpath(int u) {int x = tpn[u],y = btn[u];s.erase(hv[x]);Data tmp = sgt.query(1,1,n,dfn[x],dfn[y]); hv[x] = tmp.v;llong tmp2 = sgt2.query(1,1,n,dfn[x],dfn[y]); hv[x] = max(hv[x],tmp2);s.insert(hv[x]); } void addvpath(int u,int v,llong w) {sgt.addb(1,1,n,dfn[u],dfn[v],w);sgt2.add(1,1,n,dfn[u],dfn[v],w);calcpath(u); } void addpath(int u0,int v0,llong w) {int u = u0,v = v0;while(tpn[u]!=tpn[v]){if(dep[tpn[u]]>dep[tpn[v]]) {addvpath(tpn[u],u,w); u = fa[tpn[u]];}else {addvpath(tpn[v],v,w); v = fa[tpn[v]];}}if(dep[u]>dep[v]) swap(u,v);if(u!=v) {addvpath(idfn[dfn[u]+1],v,w);}a[u] += w; sgt.upd(1,1,n,dfn[u]); sgt2.add(1,1,n,dfn[u],dfn[u],w); calcpath(u);int x = fa[tpn[u]];while(x){lt[x].erase(sa[tpn[u]]);Data tmp = sgt.query(1,1,n,dfn[tpn[u]],dfn[btn[u]]); sa[tpn[u]] = tmp.lv;lt[x].insert(sa[tpn[u]]);llong tmp1 = h[x]; h[x] = lt[x].getmx(); sgt.upd(1,1,n,dfn[x]); sgt2.add(1,1,n,dfn[x],dfn[x],h[x]-tmp1);if(ltn[x]>=2){llong tmp2 = h2[x]; h2[x] = lt[x].getmx2();sgt2.add(1,1,n,dfn[x],dfn[x],h2[x]-tmp2);}calcpath(x);u = x; x = fa[tpn[x]];} }int main() {scanf("%d%d",&n,&q);for(int i=1; i<n; i++){int u,v; scanf("%d%d",&u,&v);addedge(u,v); addedge(v,u);}dep[1] = 1; dfs1(1);tpn[1] = 1; dfs2(1);for(int i=1; i<=q; i++){char opt[5]; scanf("%s",opt); int u,v,w;if(opt[0]=='+') {scanf("%d%d%d",&qr[i].u,&qr[i].v,&qr[i].w); u = qr[i].u,v = qr[i].v,w = qr[i].w;}else {int id; scanf("%d",&id); u = qr[id].u,v = qr[id].v,w = -qr[id].w;}addpath(u,v,w);printf("%lld\n",s.getmx());}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 4732 UOJ #268 [清华集训2016]数据交互 (树链剖分、线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。