Untitled
unknown
c_cpp
22 days ago
3.5 kB
2
Indexable
Never
#include <bits/stdc++.h> using namespace std ; #ifndef ONLINE_JUDGE #include "debugger.cpp" #else #define debug(...) #define debugArr(...) #define show(...) #endif template<typename... T>void read(T&... args) {((cin >> args), ...);} template<typename... T>void print(T&&... args) {((cout << args ), ...);} template <class T> using V = vector<T>; #define pb push_back typedef long long ll ; typedef array<int, 2> pi ; typedef vector<int> vi ; #define len(v) (int)v.size() #define FOR( i , debut, fin) for( ll i = debut ; i<fin ; i++ ) #define all(x) x.begin(), x.end() #define getunique(vt) vt.erase(unique(all(vt)), vt.end()) void YES(bool x) { if (x) cout << ("Yes\n"); else cout << ("No\n"); } const int MAX_MASK = (1 << 26) + 1; void input_output(); const int N = 3e5 + 10; int n ; vector<pi>adj[N]; vi nodes ; int depth[N] , parent[N] , pfxor[N] , in[N] , out[N] ,big[N] ; int freq[MAX_MASK] ; int timer = -1 ; void calsz ( int nd , int pr , int xpf ){ depth[nd] = 1 ; pfxor[nd] = xpf ; in[nd] = ++timer ; nodes.push_back(nd); int mx = -1 , u = -1 ; for ( auto &[ch,_]: adj[nd]){ if ( ch == pr ) continue; calsz(ch , nd , xpf ^ _ ); parent[ch] = nd ; depth[nd] += depth[ch]; if (mx < depth[ch]) { u = ch ; mx = depth[ch]; } } out[nd] = timer ; big[nd] = u; } ll ans = 0 ; void smalltobig(int node, int p, int keep = 1) { for ( auto &[ch,w]:adj[node]){ if ( ch == p or ch == big[node] )continue; else smalltobig(ch,node,0); } if ( big[node] != -1 ) smalltobig(big[node],node,1); int prfparent =pfxor[node] ; int needed1 = prfparent ; ans += freq[needed1] ; for ( int bt = 0 ; bt < 26 ; bt++ ){ int x = 1LL << bt ; int need2 = prfparent ^ x ; ans += freq[need2] ; } freq[prfparent]++ ; for ( auto &[ch,_] :adj[node]){ if ( ch == p or ch == big[node] ) continue; for ( int i = in[ch]; i <= out[ch] ; i++ ){ int nodehere = nodes[i]; ans += freq[pfxor[nodehere]]; for ( int j = 0 ; j < 26 ; j++ ){ int x = 1LL << j ; int need2 = pfxor[nodehere] ^ x ; ans += freq[need2]; } } for ( int i = in[ch] ; i <= out[ch] ;i++ ){ int nodehere = nodes[i]; freq[pfxor[nodehere]]++ ; } } if ( keep == 0 ) { for (int i=in[node];i<=out[node];++i) { int nodehere=nodes[i]; freq[pfxor[nodehere]]--; } } } void solve(){ read (n); ans = 0 ; timer = -1 ; FOR (i , 0 , n-1 ){ int u , v ; char a ; read ( u , v , a ); int msk = 1LL << (a- 'a') ; adj[u].push_back({v,msk}); adj[v].push_back({u,msk}); } pfxor[0] = 0 ; calsz(1 , 0 , 0 ); smalltobig(1,0); print(ans); } int32_t main() { input_output(); int t = 1; for ( int i = 1 ; i <= t ; i++ ){ show("------- Case " , i, "------- : " ); solve(); show("---------------------- .\n \n "); } double Time_elapsed= 1.0 * clock() / CLOCKS_PER_SEC ; debug(Time_elapsed); } void input_output() { cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0) ; #ifndef ONLINE_JUDGE freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("err.txt", "w", stderr); #endif }
Leave a Comment