[数据结构与算法]*Codeforces Round #778 (Div. 1 + Div. 2 based on Technocup 2022 Final Round)

Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)

补题：

昨天的CF题目挺好，可惜我不会写。

D（Potion Brewing Class）：

经过理解，我们知道，设根的值为$1$，在模意义下，引入逆元概念，我们可以一次$dfs$推出所有数的值。

尽管我们现在求出的这些数都是整数，但是，它们实际上是一连串分数的乘积，为了将它们统一地化成整数，我们需要求出它们分母的最小公倍数。

由于这些分数过于庞大，我们只能借助算数基本定理，用素因数分解后各素因数的指数来表示它们。

在$2?10^5$内，素数约有$10^4$个，也就是说，我们需要用一个长为$10^4$的数组来表示一个分数，如果为树上的每个点安排一个这么大的数组。这无论是在时间上还是在空间上都不好维护。

但是，由于我们的工作是在递推中进行的，我们可以让所有树上的所有节点共用一个数组（$arr$）。

由于父节点和子节点的值是很接近的（实际上，可以通过乘以或除以他们的边权得到），所以，对$arr$稍加修改就可以得到下一个节点的数组。访问完第一个子节点后，撤销掉刚刚所做的修改，$arr$又回到了原来的模样，因此可以用同样的办法访问下一个子节点。

因为我们要求分母的最大公倍数$lcm$（注意，这也是一个数组），因此我们关心$arr$中小于0的指数。注意，我们不需要每次遍历整个$arr$来更新最大公倍数，我们只要在arr更新的时候去更新$lcm$就行了。

代码：

#include<bits/stdc++.h>
#define mod 998244353
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

int tot,head[200010],ans[200010],inv[200010],arr[200010],lcm[200010];
struct edge{
	int v,x,y,nxt;
}e[400010];
vector<int>fac[200010];
void add(int u,int v,int x,int y){
	tot++;
	e[tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[tot].x=x;
	e[tot].y=y;
}
void update(int x,int y){
	int t=x;
	for(int i:fac[t]){
		while(x%i==0){
			x/=i;
			arr[i]+=y;
		}
		if(y<0) lcm[i]=min(lcm[i],arr[i]);
	}
}
void dfs(int u,int f){
	for(int i=head[u];~i;i=e[i].nxt){
		int v=e[i].v,x=e[i].x,y=e[i].y;
		if(v==f) continue;
		ans[v]=1ll*ans[u]*inv[x]%mod*y%mod;
		update(y,1);update(x,-1);   //乘以y，除以x 
		dfs(v,u);
		update(x,1);update(y,-1);  //撤销掉之前的操作（回溯技巧） 
	}
}
int q_pow(long long x,long long y){
	int res=1;
	while(y){
		if(y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return res;
} 
void solve(){
	int n;cin>>n;
	memset(head,-1,4*(n+10));
	tot=0;
	for(int i=1;i<n;i++){
		int u,v,x,y; cin>>u>>v>>x>>y;
		add(u,v,x,y);
		add(v,u,y,x);
	}
	ans[1]=1;
	dfs(1,0);
	int res=0,mul=1;
	for(int i=1;i<=n;i++){
		res+=ans[i];
		if(res>=mod) res-=mod;
		if(lcm[i]<0){
			mul=1ll*mul*q_pow(i,-lcm[i])%mod;
			lcm[i]=0; 
		}
		arr[i]=0;
	}
	res=1ll*res*mul%mod;
	cout<<res<<"\n";
}
signed main(){
	fst;
	for(int i=2;i<=200000;i++){
		if(fac[i].empty()){
			for(int j=i;j<=200000;j+=i){
				fac[j].push_back(i);     //埃氏筛求每个数的质因数 
			}
		}
	}
	inv[1]=1;
	for(int i=2;i<=200000;i++){
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;  //线性递推出每个数的逆元 
	}
	int t;cin>>t;
	while(t--) solve();
} 

**E ** Arithmetic Operations

这个题的英文题解说得很好，https://codeforces.com/blog/entry/100127。

没有英文障碍的同学可以点进去看看，有英文障碍的同学建议回去记单词。