题解--路径权值

· · 题解

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)。 

#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;
}