ZR 集训 Day5 - 树上信息维护 · ooliver

ZR 集训 Day5 - 树上信息维护 CF1009F Dominant Indices 长链剖分模板题，和重链剖分一样，只不过把重儿子的定义换成了深度最大的儿子。对于一点的深度的定义，是这个点与这个点子树内叶子节点距离的最大值加一。当 DFS 至一个点时，我们用常数的复杂度将其重儿子的 DP 值转移给它，并暴力地将其他儿子合并过来。因为每个点只会在一条链中被暴力合并，所以复杂度是线性的。代码： C++ #include using namespace std; const int N=1e6+5; int n; int dep[N],son[N],fa[N],ans[N]; vector t[N],dp[N]; void dfs1(int u,int f){ fa[u]=f; for(int v:t[u]){ if(v==f) continue; dfs1(v,u); if(dep[v]>dep[son[u]]) son[u]=v; } dep[u]=dep[son[u]]+1; } void dfs2(int u){ if(son[u]){ dfs2(son[u]); swap(dp[son[u]],dp[u]); ans[u]=ans[son[u]]+1; } dp[u].push_back(1); for(int v:t[u]){ if(v==fa[u]||v==son[u]) continue; dfs2(v); for(int i=0;idp[u][dep[u]-ans[u]-1]||(dp[u][dep[u]-(i+1)-1]==dp[u][dep[u]-ans[u]-1]&&i+1>n; for(int i=1,u,v;i>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1,0); dfs2(1); for(int i=1;i `#include using namespace std; const int N=1e6+5; int n; int dep[N],son[N],fa[N],ans[N]; vectorint> t[N],dp[N]; void dfs1(int u,int f){ fa[u]=f; for(int v:t[u]){ if(v==f) continue; dfs1(v,u); if(dep[v]>dep[son[u]]) son[u]=v; } dep[u]=dep[son[u]]+1; } void dfs2(int u){ if(son[u]){ dfs2(son[u]); swap(dp[son[u]],dp[u]); ans[u]=ans[son[u]]+1; } dp[u].push_back(1); for(int v:t[u]){ if(v==fa[u]||v==son[u]) continue; dfs2(v); for(int i=0;idep[v];i++){ dp[u][dep[u]-(i+1)-1]+=dp[v][dep[v]-i-1]; if(dp[u][dep[u]-(i+1)-1]>dp[u][dep[u]-ans[u]-1]||(dp[u][dep[u]-(i+1)-1]==dp[u][dep[u]-ans[u]-1]&&i+1ans[u])) ans[u]=i+1; } } if(dp[u][dep[u]-ans[u]-1]1) ans[u]=0; } signed main(){ cin>>n; for(int i=1,u,v;in;i++){ cin>>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1,0); dfs2(1); for(int i=1;in;i++) coutans[i]"\n"; return 0; }` P3806 【模板】点分治点分治模板。点分治的核心是以当前递归子树的重心为根进行递归、操作，这样树的深度最大为 \log 级别，就可以对经过中心的链进行暴力处理。在这道题中，我们要求出 m 次询问：树上是否存在树上距离为 k 的点对。可以用一个桶来维护。新访问一个子树的链时，先通过桶统计之前子树有没有符合条件的链，再把当前子树的链长度添加到桶中。代码： C++ #include using namespace std; #define int long long const int N=1e4+5; const int K=1e7+5; int n,m,rt,sum,tot,ptot; int siz[N],f[N],vis[N],qry[105],ans[105],q[N],p[N]; bool jdg[K]; struct node{int v,w;}; vector t[N]; void getrt(int u,int fa){ siz[u]=1,f[u]=0; for(node x:t[u]){ int v=x.v; if(v==fa||vis[v]) continue; getrt(v,u); siz[u]+=siz[v]; f[u]=max(f[u],siz[v]); } f[u]=max(f[u],sum-siz[u]); if(f[u]1e7) return; p[++ptot]=dis; for(node x:t[u]){ int v=x.v,w=x.w; if(v==fa||vis[v]) continue; getdis(v,u,dis+w); } } void cal(int u){ tot=0,q[++tot]=0,jdg[0]=1; for(node x:t[u]){ int v=x.v,w=x.w; if(vis[v]) continue; ptot=0; getdis(v,u,w); for(int i=1;i=p[i]&&jdg[qry[j]-p[i]]) ans[j]=1; } } for(int i=1;i>n>>m; for(int i=1;i>u>>v>>w; t[u].push_back({v,w}); t[v].push_back({u,w}); } for(int i=1;i>qry[i]; sum=n,rt=0,f[0]=1e9; getrt(1,0); solve(rt); for(int i=1;i `#include using namespace std; #define int long long const int N=1e4+5; const int K=1e7+5; int n,m,rt,sum,tot,ptot; int siz[N],f[N],vis[N],qry[105],ans[105],q[N],p[N]; bool jdg[K]; struct node{int v,w;}; vectornode> t[N]; void getrt(int u,int fa){ siz[u]=1,f[u]=0; for(node x:t[u]){ int v=x.v; if(v==fa||vis[v]) continue; getrt(v,u); siz[u]+=siz[v]; f[u]=max(f[u],siz[v]); } f[u]=max(f[u],sum-siz[u]); if(f[u]f[rt]) rt=u; } void getdis(int u,int fa,int dis){ if(dis>1e7) return; p[++ptot]=dis; for(node x:t[u]){ int v=x.v,w=x.w; if(v==fa||vis[v]) continue; getdis(v,u,dis+w); } } void cal(int u){ tot=0,q[++tot]=0,jdg[0]=1; for(node x:t[u]){ int v=x.v,w=x.w; if(vis[v]) continue; ptot=0; getdis(v,u,w); for(int i=1;iptot;i++){ for(int j=1;jm;j++){ if(qry[j]>=p[i]&&jdg[qry[j]-p[i]]) ans[j]=1; } } for(int i=1;iptot;i++){ q[++tot]=p[i]; jdg[p[i]]=1; } } for(int i=1;itot;i++) jdg[q[i]]=0; } void solve(int u){ vis[u]=1; cal(u); for(node x:t[u]){ int v=x.v; if(vis[v]) continue; sum=siz[v],rt=0,f[0]=1e9; getrt(v,0); solve(rt); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;in;i++){ int u,v,w; cin>>u>>v>>w; t[u].push_back({v,w}); t[v].push_back({u,w}); } for(int i=1;im;i++) cin>>qry[i]; sum=n,rt=0,f[0]=1e9; getrt(1,0); solve(rt); for(int i=1;im;i++) cout(ans[i]?"AYE\n":"NAY\n"); return 0; }` P5351 Ruri Loves Maschera 简化题意：求出树上所有边的数量在 [L,R] 区间内的链上边权最大值之和。用点分治求出以重心为根的所有链，我们按魔法值从小到大排序，那扫到当前链的魔法值就应该是产生贡献的魔法值最大值，用一个树状数组维护之前链的长度，查询符合条件的区间即可。这里相同子树内的链可能会产生错误的贡献，所以一开始在遍历子节点时就把这个贡献减掉就行。代码： C++ #include using namespace std; #define int long long #define lowbit(x) x&-x const int N=1e5+5; int n,l,r,rt,sum,ans,idx,idx1; int siz[N],f[N],vis[N]; struct node{ int v,w; bool operator t[N]; struct BIT{ int tree[N]; vector dif; void add(int x,int k){ x++; for(int i=x;i0;i-=lowbit(i)) res+=tree[i]; return res; } void clear(){ for(node x:dif) for(int i=x.v;i>n>>l>>r; for(int i=1;i>u>>v>>w; t[u].push_back({v,w}); t[v].push_back({u,w}); } sum=n,rt=0,f[0]=1e9; getrt(1,0); solve(rt); cout `#include using namespace std; #define int long long #define lowbit(x) x&-x const int N=1e5+5; int n,l,r,rt,sum,ans,idx,idx1; int siz[N],f[N],vis[N]; struct node{ int v,w; bool operatorconst node &b)const{ return vb.v; } }p[N],p1[N]; vectornode> t[N]; struct BIT{ int tree[N]; vectornode> dif; void add(int x,int k){ x++; for(int i=x;iN;i+=lowbit(i)) tree[i]+=k; dif.push_back({x,k }); } int qry(int x){ x++; if(x0) return 0; int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tree[i]; return res; } void clear(){ for(node x:dif) for(int i=x.v;iN;i+=lowbit(i)) tree[i]-=x.w; dif.clear(); } }bit; void getrt(int u,int fa){ siz[u]=1,f[u]=0; for(node x:t[u]){ int v=x.v; if(v==fa||vis[v]) continue; getrt(v,u); siz[u]+=siz[v]; f[u]=max(f[u],siz[v]); } f[u]=max(f[u],sum-siz[u]); if(f[u]f[rt]) rt=u; } void getdis(int u,int fa,int mx,int len){ p[++idx]={mx,len}; p1[++idx1]={mx,len}; for(node x:t[u]){ int v=x.v,w=x.w; if(v==fa||vis[v]) continue; getdis(v,u,max(mx,w),len+1); } } void getsiz(int u,int fa){ siz[u]=1; for(node x:t[u]){ int v=x.v; if(v==fa||vis[v]) continue; getsiz(v,u); siz[u]+=siz[v]; } } void cal(int u){ idx=0,p[++idx]={0,0}; for(node x:t[u]){ idx1=0; int v=x.v,w=x.w; if(vis[v]) continue; getdis(v,u,w,1); sort(p1+1,p1+1+idx1); for(int i=1;iidx1;i++){ ans-=(bit.qry(r-p1[i].w)-bit.qry(l-p1[i].w-1))*p1[i].v; bit.add(p1[i].w,1); } bit.clear(); } sort(p+1,p+1+idx); for(int i=1;iidx;i++){ ans+=(bit.qry(r-p[i].w)-bit.qry(l-p[i].w-1))*p[i].v; bit.add(p[i].w,1); } bit.clear(); } void solve(int u){ vis[u]=1; cal(u); for(node x:t[u]){ int v=x.v; if(vis[v]) continue; getsiz(v,u); sum=siz[v],rt=0,f[0]=1e9; getrt(v,0); solve(rt); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>l>>r; for(int i=1;in;i++){ int u,v,w; cin>>u>>v>>w; t[u].push_back({v,w}); t[v].push_back({u,w}); } sum=n,rt=0,f[0]=1e9; getrt(1,0); solve(rt); coutans*2; return 0; }` P5904 [POI 2014] HOT-Hotels 加强版长链剖分优化 DP。设 a_{i,j} 表示点 i 子树内距离它为 j 的点的个数， b_{i,j} 表示 i 字树内满足两点距离其 LCA 相等、并且从 LCA 向上找同样距离的祖先，该祖先也是距离点 i 为 j 的祖先的无序点对的个数。可以得到答案统计与状态转移式子： \begin{aligned} ans&=\sum_{u} (b_{u,0}+\sum_{x,y\in son(u),x\not =y} \sum_i a_{x,i-1}*b_{y,i+1}) \\ a_{u,i}&=\sum_{v\in son(u)} a_{v,i-1} \\ b_{u,i}&=\sum_{v\in son(u)} b_{v,i+1} + \sum_{x,y\in son(u),x\not =y} a_{x,i-1}*a_{y,i-1}) \\ \end{aligned} 发现以上信息都可以用长链剖分优化。代码： C++ #include using namespace std; typedef long long ll; const int N=1e5+5; int n,dep[N],son[N],fa[N]; vector t[N]; ll *f[N],*g[N],pool[Ndep[son[u]]) son[u]=v; } dep[u]=dep[son[u]]+1; } void dfs2(int u){ if(son[u]){ f[son[u]]=f[u]+1; g[son[u]]=g[u]-1; dfs2(son[u]); } f[u][0]=1; ans+=g[u][0]; for(int v:t[u]){ if(v==fa[u]||v==son[u]) continue; f[v]=now,now+=dep[v]>n; for(int i=1,u,v;i>u>>v; t[u].push_back(v); t[v].push_back(u); } dfs1(1,0); f[1]=now,now+=dep[1] `#include using namespace std; typedef long long ll; const int N=1e5+5; int n,dep[N],son[N],fa[N]; vectorint> t[N]; ll *f[N],*g[N],pool[N3],*now=pool,ans; void dfs1(int u,int f){ fa[u]=f; for(int v:t[u]){ if(v==f)continue; dfs1(v,u); if(dep[v]>dep[son[u]]) son[u]=v; } dep[u]=dep[son[u]]+1; } void dfs2(int u){ if(son[u]){ f[son[u]]=f[u]+1; g[son[u]]=g[u]-1; dfs2(son[u]); } f[u][0]=1; ans+=g[u][0]; for(int v:t[u]){ if(v==fa[u]||v==son[u]) continue; f[v]=now,now+=dep[v]1; g[v]=now,now+=dep[v]1; df…