結果

問題 No.439 チワワのなる木
ユーザー vjudge1
提出日時 2024-12-22 18:09:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,782 bytes
コンパイル時間 2,199 ms
コンパイル使用メモリ 170,708 KB
実行使用メモリ 22,272 KB
最終ジャッジ日時 2024-12-22 18:09:04
合計ジャッジ時間 3,825 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define bui __builtin_popcount
#define pii pair<int,int>
#define se second
#define fi first
#define mid (l+r>>1)
const int inf=1e18;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int mod=998244353;
void prt(int x){
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else prt(x/10),putchar(x%10+'0');
}
int ksm(int x,int y){
    if(y==0)return 1;
    int k=ksm(x,y/2);
    if(y&1)return k*k%mod*x%mod;
    return k*k%mod;
}
const int N=1e5+5;
int fac[N],inv[N];
//int c(int n,int m){
//    if(m>n||m<0)return 0;
//    return fac[n]*inv[m]%mod*inv[n-m]%mod;
//}
//int C(int n){
//    return fac[2*n]*inv[n]%mod*inv[n+1]%mod;
//}
void init(){
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=ksm(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int n,aw,zc[N],w[N],ans,sz[N];
char c[N];
vector<int>v[N];
void dfs(int x,int fa){
    if(c[x]=='w')w[x]=1;
    sz[x]=1;
    int sumc=0;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
        w[x]+=w[u];
        sumc+=(sz[u]-w[u]);
        if(c[x]=='w')ans-=zc[u]*2;
    }
    if(c[x]=='w')ans+=sumc*aw-sumc,ans+=(sz[x]-1-sumc)*(n-aw);
    zc[x]=w[x]*(sz[x]-w[x]);
}
void sl(){
    cin>>n;
    cin>>c+1;
    for(int i=1;i<=n;i++)aw+=(c[i]=='w'); 
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans<<"\n";
}
signed main(){
    init();
    int t=1;
//    cin>>t;
    while(t--)sl();
    return 0;
}
0