正題

題目鏈接:https://www.luogu.com.cn/problem/P7581

---

題目大意

給出$n$個點的有邊權有根樹，$m$次詢問一個節點$x$的所有$k$級兒子兩兩之間路徑長度。

$1\le n,m\le 10^6$

---

解題思路

有根長剖，無根點分治。所以這題應該是長剖（？，先離線一下詢問

然后略微分析一下，兩兩的路徑長度所以需要合并兩棵子樹向上的路徑，合并的時候又需要記錄子樹的$k$級兒子到該節點的距離和，還有$k$級兒子個數。

所以要記錄三個東西，$f_{i,j}$表示$i$節點的$j$級兒子個數，$g_{i,j}$表示$i$節點的$j$級兒子到根的距離和，$h_{i,j}$表示$i$節點的$j$級兒子兩兩之間的路徑。

然后這三個用長剖轉移就好了。

時間復雜度$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define ll long long #define mp(x,y) make_pair(x,y) #define lowbit(x) (x&-x) using namespace std; const ll N=1e6+10,P=1e9+7; struct node{ll to,next,w; }a[N<<1]; ll n,m,tot,p[N],ls[N],ans[N],len[N],son[N],dis[N],F[N],G[N],H[N]; ll *now,*tmp,*buf,*f[N],*g[N],*h[N]; vector<pair<ll,ll> >v[N]; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dfs(ll x,ll fa){for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dis[y]=dis[x]+a[i].w;dfs(y,x);if(len[y]>len[son[x]])son[x]=y;}len[x]=len[son[x]]+1;return; } void solve(ll x,ll fa){f[x][0]=1;g[x][0]=dis[x];if(son[x]){f[son[x]]=f[x]+1;g[son[x]]=g[x]+1;h[son[x]]=h[x]+1;solve(son[x],x);}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa||y==son[x])continue;f[y]=now;now+=len[y];g[y]=tmp;tmp+=len[y];h[y]=buf;buf+=len[y];solve(y,x);for(ll j=0;j<len[y];j++){ll t1=(g[x][j+1]-f[x][j+1]*dis[x])%P;ll t2=(g[y][j]-f[y][j]*dis[x])%P;(h[x][j+1]+=t1*f[y][j]%P+f[x][j+1]*t2%P)%=P;(h[x][j+1]+=h[y][j])%=P;(g[x][j+1]+=g[y][j])%=P;f[x][j+1]+=f[y][j];}}for(ll i=0;i<v[x].size();i++){ll k=v[x][i].first,id=v[x][i].second;if(k>=len[x])ans[id]=0;else ans[id]=h[x][k];}return; } signed main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);}for(ll i=1;i<=m;i++){ll x,k;scanf("%lld%lld",&x,&k);v[x].push_back(mp(k,i));}dfs(1,1);now=f[1]=F;now+=len[1];tmp=g[1]=G;tmp+=len[1];buf=h[1]=H;buf+=len[1];solve(1,1);for(ll i=1;i<=m;i++)printf("%lld\n",(ans[i]+P)%P);return 0; }

總結

以上是生活随笔為你收集整理的P7581-「RdOI R2」路径权值【长链剖分,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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