题目大意

单点修改，路径查询

解题思路

树上点修区查，考虑树剖 $+$ 线段树

由于查询时是函数嵌套，与顶点加路径和（Vertex Add Path Sum）不同，有顺序。

对于路径 $u→v$ ，可以拆分为 $u→lca(u,v)$ 和 $lca(u,v)→v$ ，分别是走向根节点和走向叶子节点，所以树剖后建立要两棵线段树

注意事项

树剖走向根节点的情况时重儿子要最后遍历

计算时不要重复计算 $lca(u,v)$ 的贡献

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200010
#define mod 998244353
int n,q;
int a[N],b[N];
vector<int>G[N];
int fa[N],dep[N],siz[N],son[N];
void dfs1(int x,int xfa){
	fa[x]=xfa;dep[x]=dep[xfa]+1;siz[x]=1;
	for(int y:G[x])if(y!=xfa){
		dfs1(y,x);
		siz[x]+=siz[y];
		if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
	}
}
int top[N];
int tsp1,dfn1[N],_dfn1[N],tsp2,dfn2[N],_dfn2[N];
void dfs2(int x,int tp){
	dfn1[x]=++tsp1;_dfn1[tsp1]=x;
	top[x]=tp;
	if(son[x])dfs2(son[x],tp);
	for(int y:G[x])if(y!=fa[x]&&y!=son[x])
		dfs2(y,y);
}
void dfs3(int x,int tp){
	for(int y:G[x])if(y!=fa[x]&&y!=son[x])
		dfs3(y,y);
	if(son[x])dfs3(son[x],tp);
	dfn2[x]=++tsp2;_dfn2[tsp2]=x;
}

int LCA(int x,int y){
	for(;top[x]!=top[y];x=fa[top[x]])if(dep[top[x]]<dep[top[y]])swap(x,y);
	return dep[x]<dep[y]?x:y;
}

#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
#define MID ((l+r)>>1)
struct node{
	int l,r,a,b;
};

struct Seg_Tree{
	node tr[N<<2];
	int dfn[N],_dfn[N];
	
	void pushup(int p){
		tr[p].a=tr[lc(p)].a*tr[rc(p)].a%mod;
		tr[p].b=(tr[rc(p)].a*tr[lc(p)].b%mod+tr[rc(p)].b)%mod;
	}
	void build(int p,int l,int r){
		if(l==r){
			tr[p]={l,r,a[_dfn[l]],b[_dfn[l]]};
			return;
		}
		tr[p]={l,r,1,0};
		build(lc(p),l,MID);build(rc(p),MID+1,r);
		pushup(p);
	}
	void chg(int p,int pos,int a,int b){
		if(tr[p].r<pos||tr[p].l>pos)return;
		if(tr[p].l==tr[p].r){
			tr[p].a=a;
			tr[p].b=b;
			return;
		}
		chg(lc(p),pos,a,b);chg(rc(p),pos,a,b);
		pushup(p);
	}
	int query(int p,int l,int r,int x){
		if(tr[p].r<l||tr[p].l>r)return x;
		if(l<=tr[p].l&&tr[p].r<=r)return (tr[p].a*x%mod+tr[p].b)%mod;
		return query(rc(p),l,r,query(lc(p),l,r,x));
	}
}sum_up,sum_down;

int get_ans(int x,int y,int z){
	if(top[x]==top[y]){
		if(x==y)return z;
		return sum_up.query(1,sum_up.dfn[y]+1,sum_up.dfn[x],z);
	}
	int ans=get_ans(fa[top[x]],y,z);
	int l=sum_up.dfn[top[x]],r=sum_up.dfn[x];
	ans=sum_up.query(1,l,r,ans);
	return ans;
}
void solve(int x,int y,int z){
	int lca=LCA(x,y);
	int ans=z;
	for(;;x=fa[top[x]]){
		if(top[x]==top[lca]){
			if(x==lca)break;
			ans=sum_down.query(1,sum_down.dfn[x],sum_down.dfn[lca]-1,ans);
			break;
		}
		ans=sum_down.query(1,sum_down.dfn[x],sum_down.dfn[top[x]],ans);
	}
	ans=sum_down.query(1,sum_down.dfn[lca],sum_down.dfn[lca],ans);
	ans=get_ans(y,lca,ans);
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;x++,y++;
		G[x].push_back(y);G[y].push_back(x);
	}
	
	dfs1(1,0);
	tsp1=tsp2=0;
	dfs2(1,1);
	dfs3(1,1);
	
	memcpy(sum_up.dfn,dfn1,sizeof(sum_up.dfn));
	memcpy(sum_up._dfn,_dfn1,sizeof(sum_up._dfn));
	memcpy(sum_down.dfn,dfn2,sizeof(sum_down.dfn));
	memcpy(sum_down._dfn,_dfn2,sizeof(sum_down._dfn));
	
	sum_up.build(1,1,n);
	sum_down.build(1,1,n);
	
	while(q--){
		int op,p,c,d,x,y,z;cin>>op;
		if(op==0){
			cin>>p>>c>>d;p++;
			sum_up.chg(1,sum_up.dfn[p],c,d);
			sum_down.chg(1,sum_down.dfn[p],c,d);
		}
		else{
			cin>>x>>y>>z;x++,y++;
			solve(x,y,z);
		}
	}
	
	return 0;
}