题解--路径权值

### 20pts 直接用 vector 存 u 的 k-son，每次询问暴力即可。 ### 50pts 考虑 $O(n^2)$ 的动态规划：一个点的贡献等于以它为 LCA 的贡献加上它子树为 LCA 的贡献。 我们想到设 $f[u][k]$ 为 $u$ 深度为 $k$ 的答案。首先 $f[u][k]=\sum\limits_{v\in u} f[v][k-1]$。这些就是子树为 LCA 的贡献，接下来考虑如何计算它为 LCA 的贡献。 假设以 $u$ 为根，计算两个儿子 $v$ 与 $w$ 之间贡献，则产生贡献的边为红色。  我们需要两个辅助数组 $g,h$，其中 $g[u][k]$ 代表 $u$ 的 $k-son$ 到其距离和，$h[u][k]$ 代表 $u$ 有多少个 $k-son$。 这两个的转移方程显而易见：$g[u][k]=\sum\limits_{v\in u}g[v][k-1]+w(u,v)\times h[v][k-1],h[u][k]=\sum\limits_{v\in u}h[v][k-1],h[u][0]=1$，其中 $w(u,v)$ 代表边权。 转移完 $g,h$ 后，我们发现对于一个新的子树 $w$，前面的所有子树 $v$ 产生的贡献是 $g[u][k]\times h[w][k-1]$（假设 $g[u][k]$ 已被前面的所有 $v$ 更新），而 $v$ 对 $w$ 的贡献是 $h[u][k]\times (g[w][k-1]+h[w][k-1]\times w(u,w))$。 整合一下，$f[u][k]=\sum\limits_{v\in u}f[v][k-1]+g[u][k]\times h[v][k-1]+h[u][k]\times (g[v][k-1]+h[v][k-1]\times w(u,v))$，注意三个必须一起转移。 ### 80pts 似乎可以有 ODTREE王子 的线段树合并和 Time_Tears 的神奇 DSU+树状数组解法。第一种做法本来能过现在已经 MLE 了。 ## 100pts 因为 dp 数组第二维是以深度为下标，似乎可以长链剖分。 但 $g$ 数组的转移形式不利于长剖。 考虑将 $g$ 数组用树上差分进行转移，设 $dis[u]$ 为 $u$ 到根距离。则 $g$ 转移改为 $g[u][k]=\sum\limits_{v\in u}g[v][k-1],g[u][0]=dis[u]$，所有值调用时需要减去 $dis[u]\times h[u][k]$。 则 $f$ 数组转移改为 $f[u][k]=\sum\limits_{v\in u}f[v][k-1]+(g[u][k]-dis[u]\times h[u][k])\times h[v][k-1]+h[u][k]\times (g[v][k-1]-dis[u]\times h[v][k-1])$。 时间复杂度 $O(n)$。 ```cpp #include<bits/stdc++.h> using namespace std; const int maxn=1e6+5,mod=1e9+7; typedef long long ll; char __buf[1<<21],*__p1,*__p2; #define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<21,stdin),__p1==__p2?EOF:*__p1++):*__p1++) inline int read() { int __x=0,__f=1; char __c=getchar(); while(__c<'0'||__c>'9') { if(__c=='-')__f=-1; __c=getchar(); } while(__c>='0'&&__c<='9') { __x=__x*10+__c-'0'; __c=getchar(); } return __x*__f; } inline char pc(char ch,bool bj) { static char buf[1<<18],*p1=buf,*p2=buf+(1<<18); return ((bj)||(*p1++=ch)&&p1==p2)&&fwrite(p1=buf,1,p1-buf,stdout),0; } void print(ll x) { if(x>9)print(x/10); pc(x%10^48,false); } inline void printnum(ll x,int ch) { print(x),pc(ch,false); } struct edge { int next,to,v; } e[maxn]; int n,m,son[maxn],len[maxn],maxd[maxn]; ll tmp[maxn*3],*f[maxn],*g[maxn],*h[maxn],*id=tmp,ans[maxn],dis[maxn],hd[maxn],cnt;//注意一些数组需要开 long long vector<int> q[maxn],qi[maxn]; void addedge(int x,int y,int z) { e[++cnt].next=hd[x]; e[cnt].to=y; e[cnt].v=z; hd[x]=cnt; } void dfs(int u,int fa) { for(register int i=hd[u]; i; i=e[i].next) { int j=e[i].to; dis[j]=dis[u]+e[i].v; dfs(j); if(maxd[j]>maxd[son[u]])son[u]=j; } maxd[u]=maxd[son[u]]+1; } void dp(int u) { if(son[u])f[son[u]]=f[u]+1,g[son[u]]=g[u]+1,h[son[u]]=h[u]+1,dp(son[u]);//先走长儿子 g[u][0]=dis[u],h[u][0]=1; for(register int i=hd[u]; i ; i=e[i].next) { int j=e[i].to; if(j==son[u])continue; f[j]=id,id+=maxd[j],g[j]=id,id+=maxd[j],h[j]=id,id+=maxd[j]; dp(j); for(register int k=1; k<=maxd[j]; k++) { f[u][k]=(f[u][k]+f[j][k-1]+(g[u][k]-dis[u]*h[u][k]%mod+mod)%mod*h[j][k-1]%mod+h[u][k]*(g[j][k-1]-dis[u]*h[j][k-1]%mod+mod)%mod)%mod; g[u][k]=(g[u][k]+g[j][k-1])%mod; h[u][k]=(h[u][k]+h[j][k-1])%mod;//将轻儿子的信息合并上去 } } for(register int i=0; i<q[u].size(); i++)if(q[u][i]<maxd[u])ans[qi[u][i]]=f[u][q[u][i]];//长剖必须离线求答案 } int main() { int x,y,z; n=read(),m=read(); for(register int i=1; i<n; i++) { x=read(),y=read(),z=read(); addedge(x,y,z); } dfs(1); for(register int i=1; i<=m; i++) { x=read(),y=read(); q[x].push_back(y),qi[x].push_back(i); } f[1]=id,id+=maxd[1],g[1]=id,id+=maxd[1],h[1]=id,id+=maxd[1]; dp(1); for(register int i=1; i<=m; i++)printnum(ans[i],'\n'); pc(0,1); return 0; } ```