计算每条边被多少路径经过,再将这个值生成一个树,顺便计算一开始的距离和
对生成的树进行树上倍增,然后对每个询问求路径长度(是新建的树的路径长度)
用长度乘w就是改变的权值和了
注意可能会有负数要加成正数
#include<iostream>
#include<string.h>
using namespace std;
const int mod=1000000007;
int n,m,fa[100001][20],ce[100001],cnt=1,dep[100001];
long long dis[100001][20],son[100001],sum=0;//dis是边权权值距离
struct edge{
int t,next;
long long d,s;
}e[200001];
long long bud(int);
long long getdis(int,int);
void add(int u,int v,int d){
e[cnt].d=d;
e[cnt].t=v;
e[cnt].s=0;
e[cnt].next=ce[u];
ce[u]=cnt++;
}
int main(){
//freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
ios::sync_with_stdio(false);
memset(ce,0,sizeof(ce));
memset(e,0,sizeof(e));
cin>>n;
int i,j,a,b,c;
for(i=1;i<n;i++){
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
fa[1][0]=1;
dis[1][0]=0;
dep[1]=1;
bud(1);
while(sum<0){
sum+=mod;
}
cout<<sum<<endl;
for(j=1;j<20;j++){
for(i=1;i<=n;i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
dis[i][j]=(dis[i][j-1]+dis[fa[i][j-1]][j-1])%mod;
}
}
cin>>m;
for(i=1;i<=m;i++){
cin>>a>>b>>c;
sum=(sum+c*getdis(a,b))%mod;
while(sum<0){
sum+=mod;
}
cout<<sum<<endl;
}
return 0;
}
long long getdis(int u,int v){
if(u==v) return 0;
int p,i;
long long res=0;
if(dep[u]<dep[v]) u^=v,v^=u,u^=v;
p=dep[u]-dep[v];
i=0;
while(p){
if(p&1){
res=(res+dis[u][i])%mod;
u=fa[u][i];
}
p>>=1;
i++;
}
if(u==v) return res;
for(i=19;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
res=(res+dis[u][i]+dis[v][i])%mod;
u=fa[u][i];
v=fa[v][i];
}
}
res=(res+dis[u][0]+dis[v][0])%mod;
return res;
}
long long bud(int v){
int p;
long long s=1;
for(p=ce[v];p;p=e[p].next){
if(e[p].t==fa[v][0]) continue;
fa[e[p].t][0]=v;
dep[e[p].t]=dep[v]+1;
s+=bud(e[p].t);
e[p].s=(son[e[p].t]*(n-son[e[p].t]))%mod;
sum=(sum+e[p].s*e[p].d)%mod;
dis[e[p].t][0]=e[p].s;
}
son[v]=s;
return son[v];
}