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] == 1
		w[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;
}