結果

問題 No.439 チワワのなる木
ユーザー vjudge1vjudge1
提出日時 2024-12-22 18:07:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 106 ms / 5,000 ms
コード長 1,920 bytes
コンパイル時間 1,941 ms
コンパイル使用メモリ 171,016 KB
実行使用メモリ 22,272 KB
最終ジャッジ日時 2024-12-22 18:08:03
合計ジャッジ時間 3,877 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,424 KB
testcase_01 AC 5 ms
7,552 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 5 ms
7,296 KB
testcase_04 AC 5 ms
7,424 KB
testcase_05 AC 5 ms
7,424 KB
testcase_06 AC 5 ms
7,424 KB
testcase_07 AC 5 ms
7,424 KB
testcase_08 AC 6 ms
7,424 KB
testcase_09 AC 5 ms
7,552 KB
testcase_10 AC 5 ms
7,296 KB
testcase_11 AC 5 ms
7,552 KB
testcase_12 AC 5 ms
7,424 KB
testcase_13 AC 5 ms
7,296 KB
testcase_14 AC 5 ms
7,424 KB
testcase_15 AC 6 ms
7,296 KB
testcase_16 AC 7 ms
7,680 KB
testcase_17 AC 7 ms
7,424 KB
testcase_18 AC 69 ms
11,648 KB
testcase_19 AC 65 ms
11,520 KB
testcase_20 AC 90 ms
13,056 KB
testcase_21 AC 28 ms
9,216 KB
testcase_22 AC 25 ms
8,960 KB
testcase_23 AC 94 ms
14,256 KB
testcase_24 AC 106 ms
20,992 KB
testcase_25 AC 82 ms
13,488 KB
testcase_26 AC 72 ms
13,512 KB
testcase_27 AC 82 ms
22,272 KB
権限があれば一括ダウンロードができます

ソースコード

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];
    }
    if(c[x]=='w')ans+=sumc*(aw-w[x]),ans+=(sz[x]-1-sumc)*(n-aw-(sz[x]-w[x]))+(w[x]-1)*(sz[x]-w[x]);
    zc[x]=w[x]*(sz[x]-w[x]);
//    cout<<x<<" "<<ans<<"\n";
}
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(){
//    freopen("cww.in","r",stdin);
//    freopen("cww.out","w",stdout);
    init();
    int t=1;
//    cin>>t;
    while(t--)sl();
    return 0;
}
0