普及月赛 D 有人用换根的吗？

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200001
const int MOD(998244353);

int n, q, u, v, w, ans;
int siz[MAXN], f[MAXN];

struct Edge{
	int v, w;
};
vector<Edge> e[MAXN];

int dfs(int x, int fa){
	siz[x] = 1;
	int res(0);
	for (auto i: e[x]){
		int v(i.v);
		if (v != fa){
			res = (res + dfs(v, x) + (siz[v] * i.w) % MOD) % MOD;
			siz[x] += siz[v];
		}
	}
	return res;
}

void dfs2(int x, int fa){
	for (auto i: e[x]){
		int v(i.v);
		if (v != fa){
			f[v] = f[x] + (n-(siz[v]<<1)) * i.w;
			if (f[v] < 0){
				f[v] += (llabs(f[v]) / MOD + 1) * MOD;
				f[v] %= MOD;
			}
			siz[x] = n-siz[v];
			siz[v] = n;
			dfs2(v, x);
		}
	}
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> q;
    for (int i(1); i<n; ++i){
    	cin >> u >> v >> w;
    	e[u].push_back({v, w});
    	e[v].push_back({u, w});
	}
	f[1] = dfs(1, 0);
	dfs2(1, 0);
	for (int i(1); i<=n; ++i) ans = (ans + f[i]) % MOD;
	
	while (q--){
		cin >> u >> w;
		cout << (ans + (w*n + f[u]) * 2) % MOD << '\n';
	}

    return 0;
}