gwcFO5 - Online C++0x Compiler & Debugging Tool

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define is insert
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<long long, long long>
#define X first
#define Y second
#define vi vector<int>
#define vpi vector<pair<int, int>>
#define msi multiset<int>
#define int long long
const int m83 = 998244353;
const int m97 = (int)1e9+7;
const int N = 200005;
const int K = 5;
const int inf = (int)1e18;

int n, q, pa[N], dep[N], tin[N], tout[N] ,sz[N], cid[N], ch[N], arr[N], nxt[N], curc, curid, timer = 1, pos[N];
pii a[N];
vi adj[N];

pii merge(pii f1, pii f2){
	int a = (f2.X * f1.X) % m83;
    int b = (f2.X * f1.Y + f2.Y) % m83;
    return {a,b};
}

int dfs(int u, int p) {
    sz[u] = 1;
    pa[u] = p;
    dep[u] = ( p <0 ? 0: dep[p]+1);
    int mx = 0;
    nxt[u] = 0;
    for (int v: adj[u]){
    	if(v != p){
	        int s = dfs(v,u);
	        sz[u] += s;
	        if (s > mx) {
	            mx = s;
	            nxt[u] = v;
	        }
        }
    }
    return sz[u];
}

void decompose(int u, int h){
    ch[u] = h;
    pos[u] = ++curid;
    arr[curid] = u;
    if (nxt[u]) decompose(nxt[u], h);
    for(int v: adj[u]){
    	if (v!=pa[u] && v!=nxt[u]){
    		decompose(v, v);
		}
    }
}

pii stl[4*N], str[4*N];

void build(int id, int l, int r){
	if(l == r){
		stl[id] = str[id] = a[arr[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(2*id, l, mid);
	build(2*id+1, mid+1, r);
	stl[id] = merge(stl[2*id], stl[2*id+1]);
	str[id] = merge(str[2*id+1], str[2*id]);
}


void update(int id, int l, int r, int pos, pii val){
	if(l > pos || r < pos) return;
	if(l == pos && r == pos){
		stl[id] = str[id] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(2*id, l, mid, pos, val);
	update(2*id+1, mid+1, r, pos, val);
	stl[id] = merge(stl[2*id], stl[2*id+1]);
	str[id] = merge(str[2*id+1], str[2*id]);
}

pii getl(int id, int l, int r, int u, int v){
	if(u > r || v < l) return {1, 0};
	if(u <= l && r <= v){
		return stl[id];
	}
	int mid = (l + r) >> 1;
	return merge(getl(2*id, l, mid, u, v), getl(2*id+1, mid+1, r, u, v));
}

pii getr(int id, int l, int r, int u, int v){
	if(u > r || v < l) return {1, 0};
	if(u <= l && r <= v){
		return str[id];
	}
	int mid = (l + r) >> 1;
	return merge(getr(2*id+1, mid+1, r, u, v), getr(2*id, l, mid, u, v));
}

void path(int u, int v, vpi& up, vpi& dn) {
    while (ch[u] != ch[v]){
        if (dep[ch[u]] >= dep[ch[v]]) {
            up.eb(pos[ch[u]], pos[u]);
            u = pa[ch[u]];
        }
		else{
            dn.eb(pos[ch[v]], pos[v]);
            v = pa[ch[v]];
        }
    }
    if (dep[u] <= dep[v]) {
        dn.eb(pos[u], pos[v]);
    }
	else{
        up.eb(pos[v], pos[u]);
    }
}

void solve(){
	cin >> n >> q;
	for(int i=1, x, y; i<=n; i++){
		cin >> x >> y;
		x %= m83;
		y %= m83;
		a[i] = {x, y};
	}
	for(int i=1, u, v; i<n; i++){
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	curc = 1;
	curid = 0;
	dfs(1, -1);
	decompose(1, 1);
	build(1, 1, n);
	while(q--){
		int t; cin >> t;
		if(t == 0){
			int p, x, y; cin >> p >> x >> y;
			update(1, 1, n, pos[p], {x, y});
		}
		else{
			int u, v, x; cin >> u >> v >> x;
			vpi up, dn;
			path(u, v, up, dn);
			int ca = 1, cb = 0;
			reverse(dn.begin(), dn.end());
			for(pii p : up){
				pii f = getr(1, 1, n, p.X, p.Y);
				tie(ca, cb) = merge({ca, cb}, f);
			}
			for(pii p : dn){
				pii f = getl(1, 1, n, p.X, p.Y);
				tie(ca, cb) = merge({ca, cb}, f);
			}
			int ans = (ca * x + cb) % m83;
			while(ans < 0) ans += m83;
			cout << ans << "\n";
		}
	}
}

signed main(){
//	freopen("*.INP", "r", stdin);
//    freopen("*.OUT", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tt = 1; //cin >> tt;
    while(tt--){
    	solve();
	}
}