0分求调
查看原帖
0分求调
1044166
zhangjingbo楼主2025/7/29 17:23

有没有大佬调一下我这个0分代码

求求了

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=300005;
const int M=998244353;
int n,m,ans;
int v[N],fa[N][21],d[N],w[N][55];
vector<int>ed[N];
void dfs(int x){
	v[x]=1;
	for(auto y:ed[x]){
		if(!v[y]){
			v[y]=1;
			d[y]=d[x]+1;
			fa[y][0]=x;
			for(int i=1;i<=20;i++){
				fa[y][i]=fa[fa[y][i-1]][i-1];
			}
			dfs(y);
		}
	}
}
void sum(int x,int ft,int k){
	for(auto y:ed[x]){
		if(y==ft)continue;
		w[y][k]+=w[x][k];
		sum(y,x,k);
	}
}
int lca(int u,int v){
	if(d[u]>d[v]){
		swap(u,v);
	}
	for(int i=20;i>=0;i--){
		if(d[fa[v][i]]>=d[u])v=fa[v][i];
	}
	if(u==v){
		return u;
	}
	for(int i=20;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	d[1]=1;
	dfs(1);
	for(int i=1;i<=n;i++){
		w[i][0]=1;
		for(int k=1;k<=50;k++){
			w[i][k]=(w[i][k-1])*d[i]%M;
		}
	}
	cin >> m;
	for(int i=1;i<=50;i++){
		sum(1,0,i);
	}
	for(int i=1;i<=m;i++){
		int u,v,k;
		cin >> u >> v >> k;
		int LCA=lca(u,v);
		int ans=(w[u][k]+w[v][k]-w[LCA][k]-w[fa[LCA][0]][k])%M;
        cout << (ans+M)%M << endl;
	}
	return 0;
}
2025/7/29 17:23
加载中...