結果

問題 No.2892 Lime and Karin
ユーザー 沙耶花
提出日時 2024-09-13 22:46:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 287 ms / 8,000 ms
コード長 2,254 bytes
コンパイル時間 3,933 ms
コンパイル使用メモリ 255,636 KB
最終ジャッジ日時 2025-02-24 08:04:42
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 52
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:111:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  111 |                 scanf("%d %d",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001LL
long long ans = 0;
int sz[200000];string S;
void dfs(vector<vector<int>> &E,int cv,int pv){
    sz[cv] = 1;
    rep(i,E[cv].size()){
        int to = E[cv][i];
        if(to==pv)continue;
        dfs(E,to,cv);
        sz[cv] += sz[to];
    }
}
int find_centroid(vector<vector<int>> &E,int cv,int pv,int N){
    int ret = -1;
    int ma = 0;
    rep(i,E[cv].size()){
        int to = E[cv][i];
        if(to==pv)continue;
        ret = max(ret,find_centroid(E,to,cv,N));
        ma = max(ma,sz[to]);
    }
    ma = max(ma,N-sz[cv]);
    if(ma <= N/2)return cv;
    return ret;
    
}
int get(char c){
    if(c=='0')return -1;
    return 1;
}
void get(vector<vector<int>> &E,int cv,int pv,vector<int> &ret,int sum){
    sum += get(S[cv]);
    ret.push_back(sum);
    rep(i,E[cv].size()){
        int to = E[cv][i];
        if(to==pv)continue;
        get(E,to,cv,ret,sum);
    }
}
long long Get(vector<int> a,int x){
    if(a.size()==0)return 0;
    sort(a.begin(),a.end());
    int cp = a.size()-1;
    long long ret = 0;
    rep(i,a.size()){
        while(cp!=-1 && a[i]+x+a[cp]>0)cp--;
        ret += a.size()-1 - cp;
        if(a[i]+x+a[i]>0)ret++;
    }
    
    return ret;
}
void solve(vector<vector<int>> &E,int cv){
    dfs(E,cv,-1);
    int c = find_centroid(E,cv,-1,sz[cv]);
    //cout<<cv<<' '<<c<<endl;
    assert(c!=-1);
    rep(i,E[c].size()){
        int to = E[c][i];
        rep(j,E[to].size()){
            if(E[to][j]==c){
                E[to].erase(E[to].begin()+j);
                break;
            }
        }
    }
    vector<vector<int>> lists(E[c].size()+1);
    rep(i,E[c].size()){
        get(E,E[c][i],-1,lists[i],0);
    }
    lists.back() = {0};
    
    long long ts = 0;
    rep(i,lists.size()){
        ts -= Get(lists[i],get(S[c]));
    }
    vector<int> t;
    rep(i,lists.size()){
        rep(j,lists[i].size()){
            t.push_back(lists[i][j]);
        }
    }
    ts += Get(t,get(S[c]));
    //cout<<"t"<<ts<<endl;
    ts /= 2;
    ans += ts;
    if(get(S[c])>0)ans++;
    //cout<<'a'<<ans<<endl;
    rep(i,E[c].size()){
        int to = E[c][i];
        solve(E,to);
    }
}
int main(){
    
    int n;
    cin>>n;
    vector<vector<int>> E(n);
    rep(i,n-1){
        int u,v;
        scanf("%d %d",&u,&v);
        u--;v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    cin>>S;
    solve(E,0);
    cout<<ans<<endl;
    
    return 0;
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0