求助
查看原帖
求助
691375
The_Administrator楼主2023/9/30 18:37

不知道哪错了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10,M=2*N,mod=998244353;
int idx,h[N],e[M],ne[M],c[M],n,q,nn[N],ff[N],st[N];
LL f[N],g[N],sf[N],sg[N],sumg,ans;
void add(int a,int b,int w)
{
	e[idx]=b;
	ne[idx]=h[a];
	c[idx]=w;
	h[a]==idx++;
}
void init(int u,int f)
{
	nn[u]=1,ff[u]=f;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(ff[u]==v)
			continue;
		init(v,u);
		nn[u]=nn[u]+nn[v];
	}
}
void dfs(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i],w=c[i];
		if(ff[u]==v)
			continue;
		if(st[v]==1)ans=(ans+(LL)(nn[v]+1)*(n-nn[v])%mod*2*w%mod)%mod;
		else ans=(ans+(LL)nn[v]*(n+1-nn[v])%mod*2*w%mod)%mod;
		dfs(v);
	}
}
void bj(int u)
{
	if(u==0)return;
	st[u]=1;
	bj(ff[u]);
}
int main()
{
	cin>>n>>q;
	int u,v,w;
	memset(h,-1,sizeof h);
	for(int i=1;i<n;i++)
	{
		cin>>u>>v>>w;
		add(u,v,w),add(v,u,w);
	}
	init(1,0);
	dfs(1);
	int k;
	while(q--)
	{
		cin>>k>>w;
		ans=(sumg-sg[k]+sf[k]+(LL)2*n*w+mod)%mod;
		cout<<ans<<endl;
	}
}
2023/9/30 18:37
加载中...