评测记录

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
struct node{
    int nxt,to,w;
    node(int x=0,int y=0,int z=0):nxt(x),to(y),w(z){}
}e[200010<<1];
int tot=1,head[200010],q,from,to,w;
void add_edge(int from,int to,int w){
    e[++tot]=node(head[from],to,w),head[from]=tot;
}
int n,size[200010];
long long ans;
void dfs(int u,int fa){
    size[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;if(v==fa)continue;
        dfs(v,u);
        size[u]+=size[v];
    }
}
void dfs2(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;if(v==fa)continue;
        ans=(ans+(long long)w*size[v]*(n-size[v]))%mod;
        dfs2(v,u);
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&from,&to,&w);
        add_edge(from,to,w),add_edge(to,from,w);
    }
	n++;
    while(q--){
    	scanf("%d%d",&from,&w);
        add_edge(from,n+1,w),add_edge(n+1,from,w);
    	dfs(1,0);
  	  	dfs2(1,0);
    	printf("%lld\n",ans*2%mod);
		head[from]=e[head[from]].nxt;
        head[n+1]=0;
        memset(size,0,sizeof(size));
        tot-=2;
        ans=0;
	}
    return 0;
}