倍增LCA100pts但#14TLE求优化
查看原帖
倍增LCA100pts但#14TLE求优化
1664852
Saty楼主2025/7/26 10:26
#include<iostream>
#include<cstdio>
#include<vector>
#define MAXN 300010
#define MOD 998244353
using namespace std;

inline int read() {
	int sum=0,ff=1; char ch=getchar();
	while(ch<'0' or ch>'9') { if(ch=='-') ff=-1; ch=getchar(); }
	while(ch>='0' and ch<='9') { sum=(sum*10+ch-'0'); ch=getchar(); }
	return sum*ff;
}

typedef long long ll;

int n,m;
vector<int> G[MAXN];
int f[MAXN][20];
ll dep[MAXN];
ll val[MAXN][60];
ll sum[MAXN][60];

void dfs1(int u,int pre,ll depth){
	f[u][0]=pre;
	dep[u]=depth;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v!=pre){
			dfs1(v,u,depth+1);
		}
	}
	return ;
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}

void dfs2(int u,int pre,ll k,ll now){
	now=(now+val[u][k])%MOD;
	sum[u][k]=now;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v!=pre){
			dfs2(v,u,k,now);
		}
	}
}

int solve(int x,int y,ll k){
	int lcat=lca(x,y);
	//cout<<"lca:"<<x<<" "<<y<<" "<<lcat<<endl;
	int ans=(sum[x][k]+sum[y][k])%MOD-(sum[lcat][k]+sum[f[lcat][0]][k])%MOD;
	while(ans<0) ans+=MOD;
	ans=ans%MOD;
	return ans;
}

int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		x=read(),y=read();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(1,0,0);
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i++){
		ll res=1;
		val[i][0]=1;
		for(int j=1;j<=50;j++){
			res=res*dep[i]%MOD;
			val[i][j]=res;
		}
	}
	for(ll i=1;i<=50;i++){
		dfs2(1,0,i,0);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		ll k;
		x=read(),y=read(),k=read();
		cout<<solve(x,y,k)<<endl;
	}
	return 0;
}
2025/7/26 10:26
加载中...