sakuya
我们考虑每对距离 \(d(i,j)\)（两个方向都算）在所有方案中的出现次数。
考虑捆绑法，共 \((m-1)!\)，又因为 \(i,j;j,i\)，所以出现次数就是 \(2(m-1)!\)。
问题就变成了求解出关键点对两两之间的距离。
我们考虑每条边的贡献，是边权乘以子树内的关键点数乘以子树外的关键点数，这样恰好包含了路径两端点的所有情况，是不重不漏的。
关于子树内的关键点数，可以类似于求解子树大小，外面的就是总点数减去。
然后考虑枚举每个点相连的边，乘上贡献（不应该乘上边权，只是乘上关键点数那一项）。
每次修改只需要将答案增加对应点的贡献即可。
复杂度 \(O(n+q)\)，莫名TLE。
#include<iostream>
#include<cstring>
#pragma GCC optimize(2)
using namespace std;
const int N=500010,M=2*N,mod=998244353;
template<typename T>
void read(T &x){
char c=getchar();
x=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
}
typedef long long ll;
#define Add(a,b) (a+=b)>=mod&&(a-=mod)
char num[30];
template<typename T>
void write(T x,char fg='\n'){
if(!x){
putchar('0');
putchar(fg);
return;
}
int cur=0;
while(x)num[cur++]=x%10+'0',x/=10;
while(cur--)putchar(num[cur]);
putchar(fg);
}
int n,sz[N],cnt[N],ans;
ll m;
int h[N],e[M],ne[M],idx,w[M];//don't forget memset h!
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int x,int fa){
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(j==fa)continue;
dfs(j,x);
ll tmp=1ll*sz[j]*(m-sz[j])%mod;
Add(ans,tmp*w[i]%mod);
Add(cnt[x],tmp),Add(cnt[j],tmp);
sz[x]+=sz[j];
}
}
ll qpow(ll a,int b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
read(n),read(m);
ll invm=qpow(m,mod-2);
Add(invm,invm);
memset(h+1,-1,n*4);
for(int i=1;i<n;++i){
int a,b,c;
read(a),read(b),read(c);
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=m;++i){
int a;
read(a);
sz[a]=1;
}
dfs(1,-1);
int q;
read(q);
while(q--){
int a;
ll b;
read(a),read(b);
Add(ans,cnt[a]*b%mod);
printf("%d\n",ans*invm%mod);
// write(ans*invm%mod);
}
return 0;
}