社区讨论

我爆了

灌水区参与者 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 条回复,欢迎继续交流。

正在加载回复...