5.二次求和

暴力
首先觀察詢問，樹上鏈$u\to v$點(diǎn)權(quán)加，顯然可以用樹上差分LOJ dfs序4 $O(1)$完成此操作，然后考慮對(duì)這些權(quán)值對(duì)答案的影響？
設(shè)經(jīng)過某點(diǎn)$u$符合條件的路徑條數(shù)為${\text{path}}_u$
當(dāng)$u$點(diǎn)權(quán)$+c$后，那么它對(duì)答案的貢獻(xiàn)則是${\text{path}}_u\times c$，而對(duì)于$u\to v$這條路徑來說，點(diǎn)權(quán)全部$+c$后對(duì)答案的貢獻(xiàn)是

$$\sum _{i\in u\to v}{\text{path}}_i\times c$$

如果完成${\text{path}}_u$預(yù)處理后以及最開始的答案，之后每個(gè)操作對(duì)答案的貢獻(xiàn)可根據(jù)上述方法求出。

觀察題目數(shù)據(jù)范圍發(fā)現(xiàn)前$50\text{pts}$的$n\le 2000$，這就很容易了，暴力枚舉每個(gè)點(diǎn)為起點(diǎn)，把所有路徑都拿出來然后記錄一下每條路徑，當(dāng)一條路徑符號(hào)題意時(shí)維護(hù)${\text{path}}_u$即可。

然后觀察到$60\text{pts}$的點(diǎn)是一條鏈，可以亂搞一下在騙$10\text{pts}$

#include<queue> #include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=2010; constexpr ll mod=1e9+7; int h[N],e[2*N],ne[2*N],idx; void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} int n,m,L,R; int a[N],d[N]; bool vis[N]; ll b[N],ans,path[N]; int pre[N]; void bfs(int S) {memset(d,0,sizeof(int)*(n+1));memset(pre,0,sizeof(int)*(n+1));memset(b,0,sizeof(ll)*(n+1));memset(vis,0,sizeof(bool)*(n+1));queue<int> q;q.push(S); d[S]=0;b[S]=a[S];vis[S]=1;while(q.size()){int u=q.front();q.pop();for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(!vis[v]){d[v]=d[u]+1;b[v]=(b[u]+a[v])%mod;pre[v]=u;//記錄路徑q.push(v);vis[v]=1;}}}for(int i=1;i<=n;i++)if(L<=d[i]&&d[i]<=R) {ans=(ans+b[i])%mod;int u=i;while(u) //維護(hù)路徑path{path[u]++;u=pre[u];}} } int sz[N],fa[N],dep[N],son[N]; ll s[N]; void dfs1(int u) {dep[u]=dep[fa[u]]+1;sz[u]=1;s[u]=path[u]+s[fa[u]];// 預(yù)處理s數(shù)組for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]) continue;fa[v]=u;dfs1(v);sz[u]+=sz[v];if(sz[son[u]]<sz[v]) son[u]=v;} } int dfn[N],timestamp,top[N]; void dfs2(int u,int t) {dfn[u]=++timestamp;top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]||v==son[u]) continue;dfs2(v,v);} } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]>=dep[top[v]]) u=fa[top[u]];else v=fa[top[v]];}return dep[u]>=dep[v]?v:u; } void init(int n) {memset(h,-1,sizeof(int)*(n+1));memset(s,0,sizeof(ll)*(n+1));memset(path,0,sizeof(ll)*(n+1));memset(dfn,0,sizeof(int)*(n+1));memset(son,0,sizeof(int)*(n+1));memset(top,0,sizeof(int)*(n+1));memset(sz,0,sizeof(int)*(n+1));timestamp=idx=0;ans=0; } int main() {int T;cin>>T;while(T--){cin>>n>>m>>L>>R;init(n);--L,--R;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){int p;cin>>p;add(i,p),add(p,i);}for(int i=1;i<=n;i++) bfs(i);ans=1ll*ans*500000004%mod;for(int i=1;i<=n;i++) path[i]/=2;dfs1(1);dfs2(1,1);while(m--){int a,b,c;cin>>a>>b>>c;int anc=lca(a,b);ans=(ans+(s[a]+s[b]-s[anc]-s[fa[anc]])*c%mod)%mod;cout<<ans<<'\n';}} }

點(diǎn)分治

學(xué)過點(diǎn)分治的一看就知道是個(gè)點(diǎn)分治的題，但是看到之后就懶得寫代碼又臭又長(zhǎng)

考慮如何通過點(diǎn)分治求出最初的答案以及維護(hù)出數(shù)組${\text{path}}_u$？

首先對(duì)于最初的答案顯然就是個(gè)點(diǎn)分治模板題這里不在贅述，而對(duì)于${\text{path}}_u$顯然不能像暴力一下記錄路徑然后加，這樣就沒必要分治了~~

點(diǎn)分治的技巧是花費(fèi)log的代價(jià)把任意路徑變成通過當(dāng)前根節(jié)點(diǎn)的路徑，也就是目前考慮的路徑都會(huì)穿過當(dāng)前根節(jié)點(diǎn)

既然穿過根節(jié)點(diǎn)，我們只需要在每條路徑的端點(diǎn)記錄一下，顯然如果當(dāng)前點(diǎn)是一個(gè)路徑的端點(diǎn)，那么它的祖先節(jié)點(diǎn)也需要被這條路徑覆蓋，只需要一遍dfs把子節(jié)點(diǎn)“回收”一下就能夠?qū)崿F(xiàn)將此路徑覆蓋的點(diǎn)都標(biāo)記。

不過一條路徑是有兩個(gè)端點(diǎn)的，但是點(diǎn)分治的過程（枚舉當(dāng)前子樹的端點(diǎn)，在前面的子樹中查找符合條件的另一個(gè)端點(diǎn)）只能知道當(dāng)前的一個(gè)端點(diǎn)，而另一個(gè)端點(diǎn)我們是不知道的。

比如當(dāng)前子樹$v$的一個(gè)端點(diǎn)$b$，而前面的子樹有一個(gè)端點(diǎn)$a$，也就是$a\to rt\to b$這條路徑符合條件，點(diǎn)分治的過程中我們只知道當(dāng)前子樹$v$的端點(diǎn)$b$

這里我采用先從前向后遍歷子樹（找到端點(diǎn)$b$），然后再從后往前遍歷子樹（找到端點(diǎn)$a$），不難發(fā)現(xiàn)這樣枚舉都會(huì)枚舉到$a\to rt\to b$這條路徑，并且一次是端點(diǎn)$b$，另一次是端點(diǎn)$a$（注意rt可能會(huì)多算需要減去）

對(duì)于直接到當(dāng)前根節(jié)點(diǎn)的路徑我們特殊處理即可

時(shí)間復(fù)雜度$O(\alpha n{\log }^{2}n+m\log n)$

#pragma GCC optimize(2) #include<cstring> #include<iostream> #include<algorithm> using namespace std; using ll=long long; constexpr int N=100010; constexpr ll mod=1e9+7; int h[N],h2[N],e[4*N],ne[4*N],idx; void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;} int n,m,L,R; int a[N],p[N]; int sz[N],fa[N],dep[N],son[N]; int dfn[N],timestamp,top[N]; ll s[N]; ll path[N],ans; int rt; ll fw[2][N]; int lowbit(int x){return x&-x;} void update(int i,int k,ll x){if(k<=0) return;for(;k<=n;k+=lowbit(k)) fw[i][k]=(fw[i][k]+x)%mod;} ll query(int i,int k){if(k<=0) return 0;ll res=0;for(;k;k-=lowbit(k)) res=(res+fw[i][k])%mod;return res;} struct node {int d,u;ll w; }d[N]; ll b[N];int cnt; bool del[N]; void dfs_rt(int u,int fa,int tot)//找重心 {sz[u]=1;int mx=0;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_rt(v,u,tot);sz[u]+=sz[v];mx=max(mx,sz[v]);}mx=max(mx,tot-sz[u]);if(2*mx<=tot) rt=u; } void dfs_sz(int u,int fa)//處理sz {sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_sz(v,u);sz[u]+=sz[v];} } void dfs_dist(int u,int fa,int dist,ll w)//找路徑 {w%=mod;d[++cnt]={dist,u,w};for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_dist(v,u,dist+1,w+a[v]);} } void dfs_fw(int u,int fa,int dist,ll w)//清空樹狀數(shù)組 {w%=mod;update(0,dist,-w);update(1,dist,-1);for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_fw(v,u,dist+1,w+a[v]);} } void dfs_add(int u,int fa) {for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_add(v,u);b[u]+=b[v];b[u]%=mod;}path[u]+=b[u];path[u]%=mod; } void dfs_b(int u,int fa)//清空b數(shù)組 {b[u]=0;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_b(v,u);} } void dfs_calc(int u,int fa,int dist,ll w)//到當(dāng)前根節(jié)點(diǎn)特殊路徑 {w%=mod;if(L<=dist&&dist<=R) b[u]++,ans=(ans+w)%mod;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa||del[v]) continue;dfs_calc(v,u,dist+1,w+a[v]);} } void work(int u,int tot) {dfs_rt(u,0,tot);u=rt;dfs_sz(u,0);del[u]=1;//順著子樹for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(del[v]) continue;cnt=0;// 指針dfs_dist(v,u,1,a[v]);for(int k=1;k<=cnt;k++) ans=(ans+query(0,R-d[k].d)-query(0,L-1-d[k].d))%mod;for(int k=1;k<=cnt;k++) {int tmp=query(1,R-d[k].d)-query(1,L-1-d[k].d);ans=(ans+1ll*d[k].w%mod*tmp%mod)%mod;b[u]-=tmp;//防止當(dāng)前根節(jié)點(diǎn)重復(fù)算b[d[k].u]+=tmp;}for(int k=1;k<=cnt;k++)update(0,d[k].d,d[k].w+a[u]),update(1,d[k].d,1);}dfs_fw(u,0,0,a[u]);//逆子樹for(int i=h2[u];i!=-1;i=ne[i]){int v=e[i];if(del[v]) continue;cnt=0;// 指針dfs_dist(v,u,1,a[v]);for(int k=1;k<=cnt;k++) {int tmp=query(1,R-d[k].d)-query(1,L-1-d[k].d);b[d[k].u]+=tmp;}for(int k=1;k<=cnt;k++)update(0,d[k].d,d[k].w+a[u]),update(1,d[k].d,1);}dfs_calc(u,0,0,a[u]);dfs_add(u,0);dfs_fw(u,0,0,a[u]); dfs_b(u,0);for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(del[v]) continue;work(v,sz[v]);}} //==================================================點(diǎn)分治 void dfs1(int u) {dep[u]=dep[fa[u]]+1;sz[u]=1;s[u]=(path[u]+s[fa[u]])%mod;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]) continue;fa[v]=u;dfs1(v);sz[u]+=sz[v];if(sz[son[u]]<sz[v]) son[u]=v;} } void dfs2(int u,int t) {dfn[u]=++timestamp;top[u]=t;if(son[u]) dfs2(son[u],t);for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(v==fa[u]||v==son[u]) continue;dfs2(v,v);} } int lca(int u,int v) {while(top[u]!=top[v]){if(dep[top[u]]>=dep[top[v]]) u=fa[top[u]];else v=fa[top[v]];}return dep[u]>=dep[v]?v:u; } //================================================== 樹剖求lca void init(int n) {memset(h,-1,sizeof(int)*(n+1));memset(h2,-1,sizeof(int)*(n+1));memset(path,0,sizeof(ll)*(n+1));memset(s,0,sizeof(ll)*(n+1));memset(dfn,0,sizeof(int)*(n+1));memset(son,0,sizeof(int)*(n+1));memset(top,0,sizeof(int)*(n+1));memset(sz,0,sizeof(int)*(n+1));memset(del,0,sizeof(bool)*(n+1));timestamp=idx=0;ans=0; } int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d%d%d",&n,&m,&L,&R);init(n);--L,--R;for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=2;i<=n;i++) scanf("%lld",&p[i]);for(int i=2;i<=n;i++) add(h,i,p[i]),add(h,p[i],i);//順著子樹for(int i=n;i>=2;i--) add(h2,i,p[i]),add(h2,p[i],i);//逆著子樹work(1,n);dfs1(1);dfs2(1,1);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);int anc=lca(a,b);ans=(ans+(s[a]+s[b]-s[anc]-s[fa[anc]])*c%mod)%mod;ans=(ans+mod)%mod;printf("%lld\n",ans);}} }

這題真蛋疼，寫完還因?yàn)槌?shù)太大（點(diǎn)分治9次dfs）TLE了，吸氧才AC
AcWing 3261. 二次求和吸氧過了，官網(wǎng)還是TLE，80pts

要加油哦~

總結(jié)

以上是生活随笔為你收集整理的2018CCF-CSP 5.二次求和（点分治）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。