$$\text{C}$$

$\text{[Problem?Discription]}$

給定一棵以 $1$ 為根的樹，記 $a_i$ 表示節點 $i$ 的權值， $\text{lca(}i,j)$ 表示節點 $i$ 和 $j$ 的最近公共祖先，求下面矩陣的行列式，對 $998244353$ 取模。

$$A=\left(\begin{array}{cccc}{a}_{\text{lca(1,1)}}& a_{\text{lca(1,2)}}& \dots & a_{\text{lca(1,n)}}\\ a_{\text{lca(2,1)}}& a_{\text{lca(2,2)}}& \dots & a_{\text{lca(2,n)}}\\ & \dots & \dots & \\ a_{\text{lca(n,1)}}& \dots & \dots & a_{\text{lca(n,n)}}\end{array}\right)$$

$\text{[Analysis]}$

線代題。

隨便取出一個葉子節點 $u$，其實有 $\text{lca(v,u)}=\text{lca(v,fa(u))}$，其中 $v\ne u,\text{fa(u)}$ 表示 $u$ 的父親。

不妨設 $u=n$。

$$\text{det}A=\left|\begin{array}{cccc}{a}_{\text{lca(1,1)}}& a_{\text{lca(1,2)}}& \dots & a_{\text{lca(1,n)}}\\ a_{\text{lca(2,1)}}& a_{\text{lca(2,2)}}& \dots & a_{\text{lca(2,n)}}\\ & \dots & \dots & \\ a_{\text{lca(n,1)}}& \dots & \dots & a_{\text{lca(n,n)}}\end{array}\right|=\left|\begin{array}{cccc}{a}_{\text{lca(1,1)}}& a_{\text{lca(1,2)}}& \dots & a_{\text{lca(1,n)}}?a_{\text{lca(1,fa(n))}}\\ a_{\text{lca(2,1)}}& a_{\text{lca(2,2)}}& \dots & a_{\text{lca(2,n)}}?a_{\text{lca(2,fa(n))}}\\ & \dots & \dots & \\ a_{\text{lca(n,1)}}& \dots & \dots & a_{\text{lca(n,n)}}?a_{\text{lca(n,fa(n))}}\end{array}\right|=\left|\begin{array}{cccc}{a}_{\text{lca(1,1)}}& a_{\text{lca(1,2)}}& \dots & 0\\ a_{\text{lca(2,1)}}& a_{\text{lca(2,2)}}& \dots & 0\\ & \dots & \dots & \\ a_{\text{lca(n,1)}}& \dots & \dots & a_n?a_{\text{fa(n)}}\end{array}\right|$$

由 Laplace 展開，可以轉化為 $(n?1)$ 階的問題進行遞歸。最終答案就是

$$\prod _{i=1}^n\left(a_i?a_{\text{fa(i)}}\right)$$

---

$$\text{D}$$

$\text{[Problem?Discription]}$

給定一個 $n$ 個點，$(2n?2)$ 條邊的有向圖，每條邊有邊權。前 $(n?1)$ 條邊構成一棵以 $1$ 為根的樹，邊的方向遠離根；后 $(n?1)$ 條邊為每個點到 $1$ 的邊。每次操作修改其中一條邊的邊權，或求出從 $u$ 到 $v$ 的最短路。

邊權為 $[1,1\times 10^6]$ 間的整數。

$\text{[Analysis]}$

從 $u$ 到 $v$ 的路徑其實很少。

1. 如果 $u$ 能沿著樹上的邊走到 $v$，那肯定沿著樹走最優。
2. 否則 $u$ 必須先回到 $1$，再從 $1$ 沿著樹走到 $v$。

維護 $1$ 沿著樹到每個點的距離（基為 $\text{Len}(u)$），當修改一條樹上邊的時候，整棵子樹內所有點的距離都將發生變化，但是變化量相同。利用樹的深度優先遍歷序（即 $\text{dfs}$ 序）連續的性質，可以用線段樹維護這個距離。

然后第 $1$ 種情況的答案其實就是 $\text{Len}(v)?\text{Len}(u)$。

這里其實利用了差分的思想，將區間求和的問題轉化為了前綴和相減。

考慮求出 $u$ 回到 $1$ 的最短路。

從直覺上講，很容易以為就是后 $(n?1)$ 條邊的權值。但是顯然 too young too simple 了。

$u$ 雖然不能沿著樹的父親回到 $1$，但它可以先到自己的某個子孫再回到 $1$。假設 $u$ 走到子樹內的節點 $w$ 再從 $w$ 回到 $1$，那么路徑的長度就是：

$$l_{u,w}+{\text{val}}_w$$

其中 $l_{u,w}$ 表示在樹上從 $u$ 到 $w$ 的距離，${\text{val}}_w$ 表示 $w$ 到 $1$ 的邊的長度。

顯然這樣是求不出來的。但是 $l_{u,w}={\text{Len}}_w?{\text{Len}}_u$，于是上面式子改寫成：

$$\left({\text{Len}}_w+{\text{val}}_w\right)?{\text{Len}}_u$$

括號內的項僅和 $w$ 有關，括號外僅和 $u$ 有關。可以用線段樹維護括號內的項，這樣就可以單次 $O(\log n)$ 地求出所需結果。

這也是一個經典的 trick。如果一個式子里含有兩個變量，那一般的數據結構都是無法維護的。分離變量是一個很好的方法。

具體實現看代碼。

考場上那些傻瓜錯誤：

1. 把有向圖看成無向圖（但其實主體思路沒有太大變化！）。
2. 沒有考慮到 $u$ 可以先走到子樹再回根。
3. 數組開太小了……

$\text{[Code]}$

int Fa[22][N],n,dep[N],q;
int u[N<<1],v[N<<1],w[N<<1],len[N];
int End[N],rec[N],dfscnt,Trans[N];
ll Len[N];
//len[i] 表示從 i 到 1 的直接邊的長度 
//Len[i] 表示初始時 1 沿著樹到 i 的總長度 struct Segment_Tree{int ls[N<<1],rs[N<<1],rt,ndcnt;ll sum[N<<1],tag[N<<1],minn[N<<1];void pushup(int o){sum[o]=sum[ls[o]]+sum[rs[o]];minn[o]=min(minn[ls[o]],minn[rs[o]]);}void pushdown(int o,int l,int r){tag[ls[o]]+=tag[o];tag[rs[o]]+=tag[o];minn[ls[o]]+=tag[o];minn[rs[o]]+=tag[o];int mid=(l+r)>>1;sum[ls[o]]+=tag[o]*(mid-l+1);sum[rs[o]]+=tag[o]*(r-mid);tag[o]=0;}void build(int &o,int l,int r,int tpe){o=++ndcnt;tag[o]=sum[o]=minn[o]=0;if (l==r){if (tpe==1) sum[o]=minn[o]=Len[Trans[l]];else sum[o]=minn[o]=Len[Trans[l]]+len[Trans[r]];return;}int mid=(l+r)>>1;build(ls[o],l,mid,tpe);build(rs[o],mid+1,r,tpe);return pushup(o);}void modify(int o,int l,int r,int p,int q,int v){if (p<=l&&r<=q){tag[o]+=v;minn[o]+=v;sum[o]+=1ll*v*(r-l+1);return;}if (tag[o]) pushdown(o,l,r);int mid=(l+r)>>1;if (p<=mid) modify(ls[o],l,mid,p,q,v);if (mid<q) modify(rs[o],mid+1,r,p,q,v);return pushup(o);}ll query(int o,int l,int r,int p){if (l==r) return sum[o];if (tag[o]) pushdown(o,l,r);int mid=(l+r)>>1;if (p<=mid) return query(ls[o],l,mid,p);else return query(rs[o],mid+1,r,p);}ll query(int o,int l,int r,int p,int q){if (p<=l&&r<=q) return minn[o];if (tag[o]) pushdown(o,l,r);int mid=(l+r)>>1;ll ans=1e18;if (p<=mid) ans=min(ans,query(ls[o],l,mid,p,q));if (mid<q) ans=min(ans,query(rs[o],mid+1,r,p,q));return ans;}
}SGT,sgt;struct edge{int nxt,to,len;
}e[N<<1];int h[N],ecnt;
void add(int u,int v,int w){e[++ecnt]=(edge){h[u],v,w};h[u]=ecnt;
}void dfs(int u,int fa){rec[u]=++dfscnt;Trans[dfscnt]=u;dep[u]=dep[fa]+1;Fa[0][u]=fa;for(int i=1;i<=20;i++)Fa[i][u]=Fa[i-1][Fa[i-1][u]];for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if (v==fa) continue;Len[v]=Len[u]+e[i].len;dfs(v,u);}End[u]=dfscnt;//記錄 dfs 序 
}
int LCA(int u,int v){if (dep[u]<dep[v]) swap(u,v);for(int i=20;i>=0;i--)if (dep[Fa[i][u]]>=dep[v])u=Fa[i][u];if (u==v) return u;for(int i=20;i>=0;i--)if (Fa[i][u]!=Fa[i][v]){u=Fa[i][u];v=Fa[i][v];}return Fa[0][v];
}ll query(int u){return sgt.query(sgt.rt,1,n,rec[u],End[u])-SGT.query(SGT.rt,1,n,rec[u]);
}
ll query(int u,int v){ll res;if (u==v) return 0;if (LCA(u,v)==u) res=SGT.query(SGT.rt,1,n,rec[v])-SGT.query(SGT.rt,1,n,rec[u]);else res=query(u)+SGT.query(SGT.rt,1,n,rec[v]);return res;
}int main(int argv,char *argc[]){n=read();q=read();for(int i=1;i<n;i++){u[i]=read();v[i]=read();w[i]=read();add(u[i],v[i],w[i]);add(v[i],u[i],w[i]);}for(int j=1;j<n;j++){int i=j+(n-1);//真實邊標號 u[i]=read();v[i]=read();//v[i] == 1w[i]=read();len[u[i]]=w[i];}dfs(1,0);SGT.build(SGT.rt,1,n,1);sgt.build(sgt.rt,1,n,2);for(int i=1;i<=q;i++){int opt=read(),s=read(),t=read();if (opt==1){if (s<n){//修改樹上的邊 SGT.modify(SGT.rt,1,n,rec[v[s]],End[v[s]],t-w[s]);sgt.modify(sgt.rt,1,n,rec[v[s]],End[v[s]],t-w[s]);//v[s] 的子樹內所有點到 1 的距離發生變化 w[s]=t;}else{sgt.modify(sgt.rt,1,n,rec[u[s]],rec[u[s]],t-len[u[s]]);len[u[s]]=t;}}else printf("%lld\n",query(s,t));}return 0;
}