BUAA XCPC 2025 Spring Training 2

$$\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;
}