fork download
copy 
  1. /* Creation Date - 30-01-2023 */  
  2. /* Creation Time - 21:13:32.27 */  
  3. #define ill 
  4. /*
  5. Written By : mafailure
  6. In the name of God 
  7. O Allah, May you grant peace and honor on Muhammad and his family.
  8. Allahumm-a-Sall-iAla Muhammad-in Wa Al-i Muhammad
  9. */
  10.  
  11. #ifdef LOCAL 
  12. #define AATIF_DEBUG
  13. #endif 
  14. /*Add -DLOCAL in 
  15. compiler command 
  16. to trigger it*/
  17.  
  18. #include<bits/stdc++.h>
  19. #include <ext/pb_ds/assoc_container.hpp> // Common file 
  20. #include <ext/pb_ds/tree_policy.hpp> 
  21. #include <functional> // for less
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24. #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25.  
  26. #define endl "\n"
  27. /*------------------------int to long long -----------------*/
  28. #ifdef ill
  29. #define int long long 
  30. #endif
  31. /*---------------------------DEBUG HELPER--------------------------------------*/
  32. template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
  33. template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
  34. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  35. template<typename T,typename K> ostream& operator<<(ostream & os,const map<T,K> & mapp){ os<<"{"; string sep=""; for(const auto& x:mapp)os<<sep<<x,sep=", "; return os<<'}'; }
  36. template <typename T> ostream & operator<<(ostream & os,const set<T> & sett){os<<'{'; string sep=""; for(const auto & x:sett)os<<sep<<x,sep=", "; return os<<'}';}
  37.  
  38. void dbg_out() { cerr << endl; }
  39. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  40.  
  41. #ifdef AATIF_DEBUG
  42. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  43. #else
  44. #define dbg(...)
  45. #endif
  46.  
  47. //#define int long long 
  48. // int dx[]={-1,1,0,0}; int dy[]={0,0,1,-1};
  49. // int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};
  50. #ifndef mod_2 
  51. long long mod = 1e9 + 7;
  52. #else 
  53. long long mod =998244353; 
  54. #endif 
  55. const double eps=1e-9;
  56. typedef vector<int> vi;
  57. typedef vector<vi> vvi;
  58. typedef vector<string> vs;
  59. typedef vector<bool> vb;
  60. typedef pair<int, int> ii;
  61. typedef vector< pair< int, int > > vii;
  62. typedef map<int, int> mii;
  63. typedef pair<int, ii> pip;
  64. typedef pair<ii, int> ppi;
  65. #define arrinp(arr,init,final,size,type) type* arr=new type[size];for(int i=init;i<final;i++)cin>>arr[i];
  66. #define cr2d(arr,n,m,t) t**arr=new t*[n];for(int i=0;i<n;i++)arr[i]=new t[m];
  67. #define w(t) int t;cin>>t; while(t--)
  68. #define takeInp(n) int n;cin>>n;
  69. #define fr(i,init,final) for(int i=init;i<final;i++)
  70. #define frr(i,init,final) for(int i=init;i>=final;i--)
  71. #define Fr(i,final) for(int i=0;i<final;i++)
  72. #define Frr(i,first) for(int i=first;i>=0;i--)
  73. #define fi first
  74. #define se second
  75. #define mp make_pair
  76. #define pb push_back
  77. #define all(c) (c).begin(),(c).end()
  78. #define rall(c) (c).rbegin(),(c).rend()
  79. #define debug(x) cerr<<">value ("<<#x<<") : "<<x<<endl;
  80. #define setb __builtin_popcount
  81. #define lsone(n) (n&(-n))
  82. #define rlsone(n) (n&(n-1))
  83. #define clr(a,b) memset(a,b,sizeof(a))
  84. #ifdef ill 
  85. const int inf =1e18; 
  86. #else 
  87. const int inf=1e9;
  88. #endif
  89. /*-----------------------------RANDOM NUMBER GENERATOR ---------------------*/
  90. #ifdef RNG 
  91. unsigned seed=chrono::high_resolution_clock::now().time_since_epoch().count();
  92. mt19937 rng(seed);
  93. #endif 
  94. /*------------------------------UNORDERED MAP HASH --------------------------------------------*/
  95. //To make unordered_map unhackable 
  96. // use it as unordered_map<int,int,custom_hash> mapp;
  97. struct custom_hash {
  98.     static uint64_t splitmix64(uint64_t x) {
  99.         /* http://x...content-available-to-author-only...i.it/splitmix64.c */
  100.         x += 0x9e3779b97f4a7c15;
  101.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  102.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  103.         return x ^ (x >> 31);
  104.     }
  105.  
  106.     size_t operator()(uint64_t x) const {
  107.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  108.         return splitmix64(x + FIXED_RANDOM);
  109.     }
  110. };
  111. /*---------------------------ORDERED SET--------------------------------------*/
  112. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  ordered_set; 
  113. /*----------------------------------------------------------------------------*/
  114. vi init(string s)
  115. {
  116. 	istringstream sin(s);
  117. 	int n;
  118. 	vi arr;
  119. 	while(sin>>n)arr.push_back(n);
  120. 	return arr;
  121. }
  122. int power(int x, int y,int mod)
  123. { 
  124. 	if(y==0)return 1;
  125. 	int u=power(x,y/2,mod);
  126. 	u=(u*u)%mod;
  127. 	if(y%2)u=(x*u)%mod;
  128. 	return u;
  129.  
  130. }
  131. int gcd(int a,int b)
  132. {
  133. 	if(a<b)return gcd(b,a);
  134. 	return (b==0?a:(a%b?gcd(b,a%b):b));
  135. }
  136. int gcd_e(int a,int b,int &x,int &y)
  137. {
  138.  
  139. 	if(b==0){x=1; y=0; return a;}
  140. 	int x1,y1;
  141. 	int p=gcd_e(b,a%b,x1,y1);
  142. 	x=y1;
  143. 	y=x1-(a/b)*y1;
  144. 	return p;
  145. }
  146. /*-----------------to solve int to long long problem-----------------*/
  147. int Min (int a,int b){return min(a,b);}
  148. int Max(int a,int b){ return max(a,b);}
  149. inline int add(int a,int b,int mod=mod){return (a+b)%mod;} 
  150. inline int sub(int a,int b,int mod=mod){return (a-b+mod)%mod;}
  151. inline int mul(int a,int b,int mod=mod){return (a*b%mod);}
  152. inline int divide(int a,int b,int mod=mod){return a*power(b,mod-2,mod)%mod;}
  153. inline int high(int a,int b){return (a>>b)&1;}
  154. //786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121 786 121
  155. /*========================CODE*****CODE****CODE======================*/
  156.  
  157. /*
  158.  Use Code submitted in ARC 60 F
  159. */
  160.  
  161.  
  162. template<const int X=2> 
  163. class StringHashing
  164. {
  165. 	using T=array<int,X> ; 
  166. 	public: 
  167. 	function<T(int,int)> get_sub; 
  168. 	function<bool(int,int,int,int)> match_two_sub; 
  169. 	vector<T> hash,pp,ipp; 
  170. 	T p,ip,mod; 
  171. 	StringHashing(int N)
  172. 	{
  173. 		/*TODO Base values of mod, p, ip needs to be updated if you are using different X*/
  174. 		mod={(int)1e9+7,(int)1e8+7}; 
  175. 		p={37,43}; 
  176. 		ip={power(p[0],mod[0]-2,mod[0]),power(p[1],mod[1]-2,mod[1])}; 
  177. 		T base_val; 
  178. 		base_val.fill(1); 
  179. 	    pp=vector<T>(N,base_val); 
  180. 	    ipp=vector<T>(N,base_val); 
  181. 		for(int i=1;i<N;i++)
  182. 		{
  183. 			for(int j=0;j<X;j++)
  184. 			{
  185. 				pp[i][j]=mul(pp[i-1][j],p[j],mod[j]); 
  186. 				ipp[i][j]=mul(ipp[i-1][j],ip[j],mod[j]); 
  187. 			}
  188. 		}
  189. 	}
  190.  
  191.  
  192. };
  193. signed main()
  194. {
  195. 	IOS
  196. 	using T=array<int,2>; 
  197. 	w(TC)
  198. 	{
  199. 		int n; 
  200. 		cin>>n; 
  201. 		vector<char> a(n); 
  202. 		fr(i,0,n)cin>>a[i];
  203. 		StringHashing<> helper(n+5);
  204. 		vector<T>hash(n); 
  205. 		vvi g(n); 
  206. 		fr(i,0,n-1){
  207. 		int u,v; cin>>u>>v; u--; v--; g[u].pb(v); 
  208. 		g[v].pb(u);}
  209.  
  210. 		function<void(int,int,int,T)>pre=[&](int u,int p,int dep,T h)
  211. 		{
  212. 			fr(i,0,2){
  213. 			hash[u][i]=add(h[i],mul((a[u]-'a'+1),helper.pp[dep][i],helper.mod[i]),helper.mod[i]);
  214. 			}
  215. 			for(auto v:g[u])
  216. 			{
  217. 				if(v!=p)pre(v,u,dep+1,hash[u]); 
  218. 			}
  219.  
  220. 		};
  221. 		pre(0,-1,1,T({0,0})); 
  222. 		vector<map<pair<int,int>,int>> mapp(n); 
  223. 		vector<int> ans(n); 
  224. 		function<void(int,int)> dfs=[&](int u,int p)
  225. 		{
  226. 			ans[u]=1;
  227. 			mapp[u][mp(hash[u][0],hash[u][1])]++;
  228. 			for(auto v:g[u]){
  229. 				if(v==p)continue;
  230. 				dfs(v,u);
  231. 				for(auto &it: mapp[v])
  232. 				{
  233. 					ans[u]+=it.se*mapp[u][it.fi]; 
  234. 					mapp[u][it.fi]+=it.se;  
  235. 				}
  236. 			}
  237.  
  238. 		};
  239. 		dfs(0,-1); 
  240. 		int q; 
  241. 		cin>>q; 
  242. 		fr(i,0,q)
  243. 		{
  244. 			int u; 
  245. 			cin>>u; 
  246. 			u--; 
  247. 			cout<<ans[u]<<endl; 
  248. 		}
  249.  
  250. 	}
  251.  
  252.  
  253.  
  254. }
  255.  
  256.  
  257.  
  258.  
Runtime error #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/urOb4Y
language:
C++14 (gcc 8.3)
created:
1 year 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!