傳送門

題意：有一棵開始時沒有結點的樹，$n$次詢問，每次新加一點并給定父結點、到父親的距離、參數$r_i$,并詢問滿足$dist(u,v)\le r_u+r_v$的點對$(u,v)$的對數。

$n\le 10^5$，強制在線

很好的一道題，并沒有江湖上傳言的那么恐怖我只寫了兩天而已

顯然我們只需要考慮新加的點的貢獻和之前加起來即可

設當前加的點為$u$

盯著這個式子：

$$dist(u,v)\le r_u+r_v$$

如果我們隨便找到$u$到$v$路徑上的一點$p$ ,可以拆成

$$dist(u,p)+dist(v,p)\le r_u+r_v$$

我們要求的就是滿足

$$dist(v,p)?r_v\le r_u?dist(u,p)$$

的$v$的個數

如果$p$固定，就可以用平衡樹瞎維護一下

然后可以枚舉$u$的祖先作為$p$統計答案

但顯然給條鏈就掛了

注意到我們這樣做的復雜度是$O(u的深度)$，可以試試點分樹

如果樹的形態是固定的，因為點分樹的性質

點分樹上兩點的$lca$在原樹上這兩點的路徑上

并且我們上面要求的恰好只是在路徑上，所以可以在點分樹上用相同的方式統計

具體實現的時候，每個點分樹上的結點$u$開棵平衡樹記錄子樹中所有點$v$的$dist(v,u)?r_v$

然后設新加的點為$x$,從$x$開始往上跳，跳到$u$時詢問$u$的平衡樹中$\le r_x?dist(x,u)$的點的個數

但這樣會算進不是簡單路徑的，所以需要記錄$u$的 某個兒子 的子樹 中的結點$v$的$dist(v,u)?r_v$的信息減一下

具體而言就是每個結點$u$再開一個平衡樹記錄子樹中的每個結點$v$的$dist(v,f{a}_u)?r_v$

但是這棵樹還會動

采用黑科技，用替罪羊樹的思想，在跳點分樹的時候如果有偏得太嚴重的點，就把整個子樹重構

說著簡單其實細節不少

因為常數大得驚人，所以內部平衡樹用了替罪羊樹

真·奧義·替罪羊套替罪羊

復雜度$O(能過)$

本題的易錯細節：

內部替罪羊重構的時候要清空$ch$數組

點分樹重構子樹的時候在原樹上只是一個連通塊，需要dfs一遍打個標記，后面只訪問有標記的點

點分樹重構子樹時要清空所有結點的一堆信息

因為要算$dist$,在點分樹重構前要先把新的子樹的根（即整個連通塊的重心）的父親接上

要記錄點分樹上每個點是父親的第幾個兒子并傳引用

在點分樹重構時暴力建平衡樹要開兩個vector并分別排序

點分樹重構不能修改$up,dis$等信息

判斷重構時要特判是整個點分樹的根的情況

要寫內存回收池

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <algorithm> #include <cassert> #define MAXN 100005 #define MAXM 200005 using namespace std; const int MOD=1e9; const double alpha=0.8; typedef long long ll; struct edge{int u,v,w;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; inline void addnode(int u,int v,int w) {e[++cnt]=(edge){u,v,w};nxt[cnt]=head[u];head[u]=cnt; } inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } int dis[MAXN],dep[MAXN],up[MAXN][20]; inline int lca(int x,int y) {if (dep[x]<dep[y]) swap(x,y);int t=dep[x]-dep[y];for (int i=0;(1<<i)<=t;i++) if (t&(1<<i)) x=up[x][i];if (x==y) return x;for (int i=19;i>=0;i--) if (up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];return up[x][0]; } inline int dist(const int& x,const int& y){return dis[x]+dis[y]-2*dis[lca(x,y)];} namespace SGT {int *pos;const int N=MAXN<<6;int bin[N],lis[N];int ch[N][2],siz[N],val[N],tot;inline int newnode(const int& v){int x=(bin[0]? bin[bin[0]--]:++tot);return ch[x][0]=ch[x][1]=0,siz[x]=1,val[x]=v,x;}inline void update(const int& x){siz[x]=siz[ch[x][0]]+1+siz[ch[x][1]];}void insert(int& x,int v){if (!x) return (void)(x=newnode(v));insert(ch[x][v>val[x]],v);update(x);if (siz[ch[x][0]]>siz[x]*alpha||siz[ch[x][1]]>siz[x]*alpha) pos=&x;}void build(int& x,int l=1,int r=lis[0]){if (l>r) return (void)(x=0);int mid=(l+r)>>1;x=newnode(lis[mid]),build(ch[x][0],l,mid-1),build(ch[x][1],mid+1,r),update(x);}void dfs(int& x){if (!x) return;dfs(ch[x][0]);bin[++bin[0]]=x,lis[++lis[0]]=val[x];dfs(ch[x][1]);x=0;}inline void rebuild(){if (pos==NULL) return;lis[0]=0,dfs(*pos),build(*pos),pos=NULL;}inline void modify(int& x,int v){insert(x,v),rebuild();}int query(int x,int v){if (!x) return 0;if (v<val[x]) return query(ch[x][0],v);return siz[ch[x][0]]+1+query(ch[x][1],v);}inline void getbuf(const vector<int>& v){lis[0]=0;for (int i=0;i<(int)v.size();i++) lis[++lis[0]]=v[i];} } using SGT::modify; using SGT::query; using SGT::getbuf; int fa[MAXN],idx[MAXN],rt[MAXN],prt[MAXN],r[MAXN],*pos; int Rt=1; vector<int> son[MAXN],sub[MAXN]; inline void addnode(int u,int f){fa[u]=f,son[f].push_back(u),idx[u]=son[f].size()-1;} inline int insert(int x) {int ans=0;for (int u=x,v=0;u;v=u,u=fa[u]){int val=r[x]-dist(x,u);ans+=query(rt[u],val)-query(prt[v],val);modify(rt[u],-val);if (v) modify(prt[v],-val);if (SGT::siz[rt[v]]>SGT::siz[rt[u]]*alpha) pos=(fa[u]? &son[fa[u]][idx[u]]:&Rt);}return ans; } bool vis[MAXN]; vector<int> block; void dfs(int u){vis[u]=1,block.push_back(u);for (int i=0;i<(int)son[u].size();i++) dfs(son[u][i]);} int siz[MAXN],maxp[MAXN]={0x7fffffff},root; void findrt(int u,int f,int sum) {siz[u]=1,maxp[u]=0;for (int i=head[u];i;i=nxt[i])if (vis[e[i].v]&&e[i].v!=f){findrt(e[i].v,u,sum);siz[u]+=siz[e[i].v],maxp[u]=max(maxp[u],siz[e[i].v]);}if (sum-siz[u]>maxp[u]) maxp[u]=sum-siz[u];if (maxp[u]<maxp[root]) root=u; } int getsiz(int u,int f) {int ans=1;for (int i=head[u];i;i=nxt[i])if (vis[e[i].v]&&e[i].v!=f)ans+=getsiz(e[i].v,u);return ans; } void build() {vis[root]=0;int u=root;sub[u].push_back(u);for (int i=head[u];i;i=nxt[i])if (vis[e[i].v]){root=0;findrt(e[i].v,0,getsiz(e[i].v,0));int v=root;addnode(v,u);build();for (vector<int>::iterator it=sub[v].begin();it!=sub[v].end();++it) sub[u].push_back(*it);}vector<int> tmp1,tmp2;for (int i=0;i<(int)sub[u].size();i++){int v=sub[u][i];tmp1.push_back(dist(v,u)-r[v]);tmp2.push_back(dist(v,fa[u])-r[v]);}sort(tmp1.begin(),tmp1.end());getbuf(tmp1),SGT::build(rt[u]);if (fa[u]){sort(tmp2.begin(),tmp2.end());getbuf(tmp2),SGT::build(prt[u]);} } int main() {read();int n=read();ll lans=0;for (int u=1;u<=n;u++){int a,c;a=read()^(lans%MOD),c=read(),r[u]=read();up[u][0]=a;for (int i=1;i<20;i++) up[u][i]=up[up[u][i-1]][i-1];dis[u]=dis[up[u][0]]+c,dep[u]=dep[up[u][0]]+1;if (u>1) addnode(u,a);addnode(u,a,c),addnode(a,u,c);printf("%lld\n",lans+=insert(u));if (pos==NULL) continue; // cerr<<"rebuild "<<*pos<<'\n';int f=fa[*pos],id=idx[*pos];dfs(*pos),root=0,findrt(*pos,0,SGT::siz[rt[*pos]]);int RT=root; // cerr<<*pos<<' '<<RT<<'\n';for (int i=0;i<(int)block.size();i++) {int v=block[i];SGT::dfs(rt[v]),SGT::dfs(prt[v]);fa[v]=idx[v]=rt[v]=prt[v]=0;son[v].clear(),sub[v].clear();}fa[RT]=f,idx[RT]=id,*pos=RT;build();block.clear();pos=NULL;} return 0; }

總結

以上是生活随笔為你收集整理的【WC2014】紫荆花之恋【替罪羊思想】【动态点分树】【替罪羊树】的全部內容，希望文章能夠幫你解決所遇到的問題。

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