結果

問題 No.439 チワワのなる木
ユーザー smiken_61smiken_61
提出日時 2016-11-13 23:59:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 189 ms / 5,000 ms
コード長 3,839 bytes
コンパイル時間 1,332 ms
コンパイル使用メモリ 151,724 KB
実行使用メモリ 36,264 KB
最終ジャッジ日時 2023-08-17 04:30:03
合計ジャッジ時間 4,148 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
12,716 KB
testcase_01 AC 6 ms
12,728 KB
testcase_02 AC 6 ms
12,856 KB
testcase_03 AC 6 ms
12,764 KB
testcase_04 AC 7 ms
12,928 KB
testcase_05 AC 6 ms
12,836 KB
testcase_06 AC 6 ms
12,720 KB
testcase_07 AC 7 ms
12,996 KB
testcase_08 AC 6 ms
12,724 KB
testcase_09 AC 6 ms
12,860 KB
testcase_10 AC 7 ms
12,792 KB
testcase_11 AC 6 ms
12,720 KB
testcase_12 AC 7 ms
12,720 KB
testcase_13 AC 7 ms
12,796 KB
testcase_14 AC 7 ms
12,892 KB
testcase_15 AC 7 ms
12,832 KB
testcase_16 AC 8 ms
12,916 KB
testcase_17 AC 7 ms
13,176 KB
testcase_18 AC 120 ms
19,852 KB
testcase_19 AC 94 ms
18,764 KB
testcase_20 AC 164 ms
22,116 KB
testcase_21 AC 34 ms
15,156 KB
testcase_22 AC 34 ms
15,512 KB
testcase_23 AC 180 ms
23,828 KB
testcase_24 AC 189 ms
33,436 KB
testcase_25 AC 86 ms
19,412 KB
testcase_26 AC 80 ms
20,416 KB
testcase_27 AC 106 ms
36,264 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

            #include <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
          #define int long long
            #define inf  1000000007
            #define pa pair<int,int>
    #define ll long long
            #define pal pair<ll,ll>
            #define ppa pair<int,pa>
            #define  mp make_pair
            #define  pb push_back
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
int gcd(int v,int b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
            //----------------kokomade temple------------
int x,y,n,m;
string s;
int keta[10]={0};


vector<int> G[100002];
vector<int> G2[100002];
vector<int> cc[100002];
vector<int> ww[100002];

void saikisaiki(int u,int mae){

	for(int i=0;i<G[u].size();i++){
		if(G[u][i]==mae) continue;
		G2[u].push_back(G[u][i]);
		saikisaiki(G[u][i],u);
	}
	
}

void make_root(int root){
saikisaiki(root,-1);
return ;
}


pa dfs(int r){
	
	if(G2[r].size()==0){
		if(s[r]=='c') return mp(1,0);
		else return mp(0,1);
	}
	pa z=mp(0,0);
	if(s[r]=='c') z.first++;
		else z.second ++ ;
	
	for(int i=0;i<G2[r].size();i++){
		pa zz=dfs(G2[r][i]);
		z.first += zz.first;
		z.second += zz.second;
		cc[r].pb(zz.first);
		ww[r].pb(zz.second);
	}
	
	return z;
}

    signed main(){
    	cin>>n;
cin>>s;
    s = "q"+s;
    	for(int i=0;i<n-1;i++){
    		int zzz,zz;
    		cin>>zz>>zzz;
    		G[zz].pb(zzz);
    		G[zzz].pb(zz);
    		
    	}
    	make_root(1);
    	
    	pa z=dfs(1);
    	int cnum=z.first,wnum=z.second;
  //  	cout<<z.first<<" "<<z.second<<endl;
    	int ans=0;
    	for(int i=1;i<=n;i++){
    		if(s[i]=='c') continue;
    		if(G2[i].size()==0) continue;
    		int cx=0,wx=0;
    		for(int j=0;j<G2[i].size();j++){
    			cx += cc[i][j];
    			wx += ww[i][j];
    			ans += cc[i][j] * (wnum-ww[i][j]-1);
    			
    		}
    		if(i!=1){
    			ans += (cnum-cx)*(wx);
    //			cout<<" "<<cnum-cx<<" "<<wx<<endl;
    		}
    		
    	}
    	cout<<ans<<endl;
    //	printf("%.10f\n",ans);
    	return 0;
    }
0