fork(1) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define rep(i,a,n) for (int i=(a);i<(n);i++)
  6. #define per(i,a,n) for (int i=(n)-1;i>=(a);i--)
  7. #define pb push_back
  8. #define mp make_pair
  9. #define all(x) (x).begin(),(x).end()
  10. #define fi first
  11. #define se second
  12. #define SZ(x) (int)x.size()
  13.  
  14. typedef long long ll;
  15. typedef double ld;
  16. typedef vector<int> vi;
  17. typedef vector<ll> vll;
  18. typedef pair<int,int> pii;
  19.  
  20. int getint() {
  21.     int x=0;
  22.     char ch;
  23.     do{ch=getchar();}while(ch <= ' ');
  24.     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
  25.     return x;
  26. }
  27.  
  28. template<typename T1,typename T2>bool umin(T1 &x,const T2&y){if(x>y)return x=y,true;return false;}
  29. template<typename T1,typename T2>bool umax(T1 &x,const T2&y){if(x<y)return x=y,true;return false;}
  30.  
  31. const int maxn=(int)3e5+10;
  32. const int maxm=(int)8e3;
  33. const int inf=(int)1e9+5;
  34. const int mod=(int)1e9+9;
  35. const ll llinf=(ll)1e18+5;
  36. const ld pi=acos(-1.0);
  37.  
  38. int a[maxn];
  39. vi g[maxn];
  40. int num[maxn];
  41. int cur;
  42. int cnt[maxn];
  43. map<pair<int,vi>,int>have;
  44.  
  45. void dfs(int v,int par=-1){
  46. 	vi c;
  47. 	rep(i,0,SZ(g[v])){
  48. 		int to=g[v][i];
  49. 		if(to==par)continue;
  50. 		dfs(to,v);
  51. 		c.pb(num[to]);
  52. 	}
  53. 	sort(all(c));
  54. 	if(!have.count(mp(a[v],c))){
  55. 		have[mp(a[v],c)]=++cur;
  56. 	}
  57. 	num[v]=have[mp(a[v],c)];
  58. 	cnt[num[v]]++;
  59. }
  60.  
  61.  
  62. int main(){
  63.     freopen("input.txt","r",stdin);
  64.     freopen("output.txt","w",stdout);
  65.  
  66.     ios_base::sync_with_stdio(0);
  67.     int n;
  68.     cin>>n;
  69.     rep(i,0,n-1){
  70.     	int x,y;
  71.     	cin>>x>>y;
  72.     	g[x].pb(y);
  73.     	g[y].pb(x);
  74.     }
  75.     rep(i,1,n+1)cin>>a[i];
  76.     dfs(1,-1);
  77.     ll res=0;
  78.     rep(i,0,maxn){
  79.     	ll x=cnt[i];
  80.     	res+=1LL*x*(x-1)/2;
  81.     }
  82.     cout<<res<<endl;
  83.     return 0;
  84. }
Runtime error #stdin #stdout #stderr 0s 10496KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/xTknI6
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!