社区讨论
我爆了
灌水区参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lul2ia2e
- 此快照首次捕获于
- 2024/04/04 18:01 2 年前
- 此快照最后确认于
- 2024/04/04 20:21 2 年前
洛谷4 月月赛 I的T4我这份代码交了n发都只WA了一个点,获得了0分的好成绩QAQ本蒟蒻现在正在自闭。大佬帮忙看看,玄关。
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void rd(int &p){
int f=1;p=0;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')p=(p<<1)+(p<<3)+c-'0',c=getchar();
p*=f;
}
void rdl(ll &p){
int f=1;p=0;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')p=(p<<1)+(p<<3)+c-'0',c=getchar();
if(f==-1)p=-p;
}
const int N=2e5+50;
int n,t1,t2;
vector<int>v[N];
ll o=1,d[N];
void dfs(int p,ll dep,int fa){
d[p]=dep;
for(int i(0);i<v[p].size();++i){
if(v[p][i]!=fa){
if((p==t2&&v[p][i]==t1)||(p==t1&&v[p][i]==t2))dfs(v[p][i],dep+o,p);
else dfs(v[p][i],dep+1ll,p);
}
}
}
void dfss(int p,ll dep,int fa){
d[p]=max(dep,d[p]);
for(int i(0);i<v[p].size();++i){
if(v[p][i]!=fa){
if((p==t2&&v[p][i]==t1)||(p==t1&&v[p][i]==t2))dfss(v[p][i],dep+o,p);
else dfss(v[p][i],dep+1ll,p);
}
}
}
ll ans(0),E,mod=998244353;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==0ll){
x=1ll,y=0ll;return a;
}
ll c=exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-(a/b)*y%mod;
if(x<0ll)x=mod-((-x)%mod);
if(y<0ll)y=mod-((-y)%mod);
x%=mod,y%=mod;
return c;
}
ll ask(ll a,ll b){
ll x,y;
ll z=exgcd(a,mod,x,y);
if(x<0ll)x=mod-((-x)%mod);x%=mod;
return x*b%mod;
}
int main(){
rd(n);
for(int i(1),x,y;i<n;++i){
rd(x),rd(y);if(i==1)t1=x,t2=y;
v[x].push_back(y);v[y].push_back(x);
}
int x(0),y(0);
dfs(1,0ll,0);
for(int i(1);i<=n;++i)if(d[i]>d[x])x=i;
dfs(x,0ll,0);
for(int i(1);i<=n;++i)if(d[i]>d[y])y=i;
dfss(y,0ll,0);
rdl(E);E=E*(ll)n%mod;
for(int i(1);i<=n;++i)ans+=d[i],ans%=mod;ans%=mod;
if(E==0ll){
for(int i(1);i<n;++i)printf("%lld\n",mod);
return 0;
}
ll z=ask(ans,E);if(z==0ll)z=mod;
printf("%lld\n",z*o%mod);
for(int i(2);i<n;++i)printf("%lld\n",z);
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...