求助,过了样例但是全wa
查看原帖
求助,过了样例但是全wa
580036
SnowTrace楼主2022/12/19 14:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,m,k;
int lca[300005][24],d[300005],pre[300005][53];
vector<int>p[300005];
void dfs1(int now,int fa){
	//cout << now << " " << fa << endl;
	lca[now][0] = fa;
	if(now == fa)d[now] = -1;
	d[now] = d[fa]+1;
	for(int i =1;i<=20;i++)lca[now][i] = lca[lca[now][i-1]][i-1];
	for(int i =0;i<p[now].size();i++){
		if(p[now][i]!=fa)dfs1(p[now][i],now);
	}
}int lcaa(int a,int b){
	if(d[a]<d[b])swap(a,b);
	int dis = abs(d[a]-d[b]);
	for(int i =0;dis;i++,dis>>=1){
		if(dis&1)a = lca[a][i];
	}if(a == b)return a;
	for(int i = 20;i>=0;i--){
		if(lca[a][i]!=lca[b][i])a=  lca[a][i],b = lca[b][i];
	}return lca[a][0];
}//倍增求lca
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>> n;
	for(int i =1;i<n;i++){
		int a,b;cin>> a >> b;
		p[a].push_back(b),p[b].push_back(a);
	}dfs1(1,1);
	for(int j=1;j<=n;j++)pre[1][j] = j;
	for(int i = 2;i<=52;i++){
		for(int j =1;j<=n;j++){
			pre[i][j] = (pre[i][j-1]+(pre[i-1][j]-pre[i-1][j-1]+mod)%mod*j%mod)%mod;
			pre[i][j] +=mod,pre[i][j]%=mod;
		}
	}//预处理幂的和
   cin>> m;
	while(m--){
		int a,b,x;
		cin>> a >> b >> x;
		x+=1;
		int y =lcaa(a,b),ans =0;
//		cout << d[a] << " " << d[b] << " " << d[y] << endl;
	//	cout<< pre[x][d[a]] << " " << pre[x][d[b]] << endl;
		if(y == 1){
			ans = (pre[x][d[a]]+pre[x][d[b]])%mod;
		}else{
			ans = (pre[x][d[a]]-pre[x][d[y]]-pre[x][d[y]-1]+pre[x][d[b]])%mod;
		}ans+=mod;ans%=mod;
	//	assert(ans<mod),assert(ans>=0);
		cout << ans << endl;
	}return 0;
}
2022/12/19 14:18
加载中...