Hash

// use as many base/mod value as you need and adjust the 

// problem : https://codeforces.com/contest/535/problem/D 
// solution: https://codeforces.com/contest/535/submission/276911762
// problem : https://drive.google.com/file/d/1qr6Nnk2Eh4bWUp09OdQ-shm1Krt8uAqB/view  [ icpc 21 preli D no ] 
// solution: mentioned below where the template section ends.
// problem : https://codeforces.com/problemset/problem/1800/G
// solution: https://codeforces.com/contest/1800/submission/196155988

const ll MAX_N = 1e6+10, mod = 2e9+63, base1 = 1e9+21, base2 = 1e9+181;
int s[MAX_N];  // 1-indexed
ll pw1[MAX_N], pw2[MAX_N], slen;

void pw_calc() {
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i < MAX_N; i++) {
        pw1[i] = (pw1[i-1] * base1) % mod;
        pw2[i] = (pw2[i-1] * base2) % mod;
    }
}

struct Hash {
    ll h1[MAX_N], h2[MAX_N];

    void init() {
        h1[0] = h2[0] = 0;
        for(int i = 1; i <= slen; i++) {
            h1[i] = (h1[i-1] * base1 + s[i]) % mod;
            h2[i] = (h2[i-1] * base2 + s[i]) % mod;
        }
    }

    inline ll hashVal(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod;
        if(hsh1 < 0) hsh1 += mod;
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod;
        if(hsh2 < 0) hsh2 += mod;
        return (hsh1 << 32) | hsh2;
    }

    inline ll hashOne(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod;
        if(hsh1 < 0) hsh1 += mod;
        return hsh1;
    }

    inline ll hashTwo(int l, int r) {
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod;
        if(hsh2 < 0) hsh2 += mod;
        return hsh2;
    }
} fw;


---------------------------------------------------------------------------

/// tree hashing ... 
/// problem : https://codeforces.com/problemset/problem/1800/G
/// solution: https://codeforces.com/contest/1800/submission/196155988

vector<int> bas = {181, 197,233,281,293};
vector<int> mod = {114802019,969832723,480566959,185749469,851370397};

bool sym[N];

array<int,5> hsh[N],dp[N];

vector<int>adj[N] , oadj[N] ;

void dfs(int nd,int lvl,int pa=0)
{
    map<vector<int>,int>cnt ;
    map<vector<int>,vector<int>>who ;
    for(int i=0; i<5; i++)
        dp[nd][i] = 1 ;
    for(int ch:adj[nd])
    {
        if(ch==pa)continue ;
        dfs(ch,lvl+1,nd) ;
        vector<int>vc ;
        for(int i=0; i<5; i++)
        {
            dp[nd][i]*=(hsh[lvl][i]+dp[ch][i]) ;
            dp[nd][i]%=mod[i] ;
            vc.PB(dp[ch][i]) ;
        }
        cnt[vc]++ ;
        who[vc].PB(ch) ;
    }
    int odd = 0 ;
    for(auto it:cnt){
        if(it.ss&1){
        ++odd ;
        for(int ch:who[it.ff])
            oadj[nd].PB(ch) ;
        }
    }
    sym[nd]=(bool)(odd<=1) ;
}

int32_t main()
{
    IOS

    for(int i=0; i<5; i++)
        hsh[0][i]=1 ;

    for(int i=1; i<N; i++)
        for(int j=0; j<5; j++)
            hsh[i][j]=bas[j]*hsh[i-1][j]%mod[j] ;

    return 0 ;
}

// template ends here.
--------------------------------










// these are some of the ac solutions 
// you can ignore them. 
---------------------------------------------------------------------------------------------------------


/// palindrome check with double hashing 

/// ac code of icpc preli 2021 D no

#include<bits/stdc++.h>
using namespace std;
#define   MP             make_pair
#define   PB             push_back
#define   nn             '\n'
#define   endl           '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   all(vec)       vec.begin(),vec.end()
#define   int            long long
#define   pii            pair<int,int>
#define   double         long double
#define   ll             long long
#define   uu             first
#define   vv             second

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int INF=1LL*1000*1000*1000*1000*1000*1000+7LL, INF2=(1LL<<62) ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;


pii operator+(pii a, ll x)     {return {a.uu + x, a.vv + x} ;}
pii operator- (pii a, ll x)     {return {a.uu - x, a.vv - x} ;}
pii operator* (pii a, ll x)     {return {a.uu * x, a.vv * x} ;}
pii operator%(pii a,ll x)     {return {a.uu%x, a.vv%x};}
pii operator+(pii x, pii y) { return {x.uu + y.uu,x.vv + y.vv} ;}
pii operator-(pii x,pii y) { return {x.uu - y.uu, x.vv - y.vv} ;}
pii operator*(pii x,pii y) { return {x.uu * y.uu , x.vv * y.vv} ;}
pii operator%(pii x,pii y) { return {x.uu % y.uu, x.vv % y.vv} ;}

const pii base = {103,101};

const pii  mod = {1000000021, 1e9 + 9 };

int n , m , test , pal ;

string s ;

vector<int>adj[N] ;

pii fh[N],bh[N],power[N];

void dfs(int nd,int pa)
{
     fh[nd]=(fh[pa]+power[pa]*s[nd-1])%mod;
     bh[nd]=(bh[pa]*base+s[nd-1])%mod;
     power[nd]=(base*power[pa])%mod;

    if(fh[nd]==bh[nd]){
        ++pal ;
    }

    for(int ch:adj[nd])
    {
        if(ch==pa)
            continue ;

        dfs(ch,nd) ;
    }
}

int32_t main()
{
    IOS

    cin>>test ;

    for(int tt=1;tt<=test;++tt)
    {
        cin>>n>>s ;

        pal=0 ;

        fh[0]={0,0};
        bh[0]={0,0};
        power[0]={1,1};

        for(int i=1;i<n;++i)
        {
            int u , v ;
            cin>>u>>v ;
            adj[u].PB(v) ;
            adj[v].PB(u) ;
        }

        dfs(1,0) ;

        int P=pal , Q=n , g=__gcd(P,Q) ;

        P/=g ;

        Q/=g ;

        // 2cout<<" pal "<<pal<<endl ;

        cout<<"Case "<<tt<<": "<<P<<"/"<<Q<<endl ;

        for(int i=0;i<=n+2;++i)
            adj[i].clear() ;

    }

    return 0 ;
}


////  ac code of facebook hackercup 
/// double hash from shefin vai with  single mod 

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
#include<climits>
#include<functional>
#include<iomanip>
using namespace std;
#define   MP             make_pair
#define   PB             push_back
#define   nn             '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   ALL(vec)       vec.begin(),vec.end()
#define   int            long long
#define   ll             long long

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int INF=1LL*1000*1000*1000*1000*1000*1000+7LL, INF2=(1LL<<62) ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

int test , a[N] , b[N] ;

int n , m , k , one , two ;

const ll MAX_N = 1e6+10, mod = 2e9+63, base1 = 1e9+21, base2 = 1e9+181;
int s[MAX_N];  // 1-indexed
ll pw1[MAX_N], pw2[MAX_N], slen;

void pw_calc() {
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i < MAX_N; i++) {
        pw1[i] = (pw1[i-1] * base1) % mod;
        pw2[i] = (pw2[i-1] * base2) % mod;
    }
}

struct Hash {
    ll h1[MAX_N], h2[MAX_N];

    void init() {
        h1[0] = h2[0] = 0;
        for(int i = 1; i <= slen; i++) {
            h1[i] = (h1[i-1] * base1 + s[i]) % mod;
            h2[i] = (h2[i-1] * base2 + s[i]) % mod;
        }
    }

    inline ll hashVal(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod;
        if(hsh1 < 0) hsh1 += mod;
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod;
        if(hsh2 < 0) hsh2 += mod;
        return (hsh1 << 32) | hsh2;
    }

    inline ll hashOne(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod;
        if(hsh1 < 0) hsh1 += mod;
        return hsh1;
    }

    inline ll hashTwo(int l, int r) {
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod;
        if(hsh2 < 0) hsh2 += mod;
        return hsh2;
    }
} fw;

int32_t main()
{
    IOS

    pw_calc() ;

    fstream Input, Output ;

    Input.open("E:/online judge/Facebook/input.txt", ios::in);

    if (!Input)
    {
        cout << "No such file" ;
    }

    Output.open("E:/online judge/Facebook/output.txt", ios::out) ;

    Input>>test ;

    for(int tt=1;tt<=test;++tt)
    {
         int n , k ;

         Input>>n>>k ;

         for(int i=0;i<=2*n+5;++i)
            a[i]=b[i]=0 ;

         for(int i=1;i<=n;++i)
            Input>>a[i] ;

         for(int i=1;i<=n;++i)
            Input>>b[i] ;

         for(int i=n+1;i<=2*n;++i)
            a[i]=a[i-n] , b[i]=b[i-n] ;

         for(int i=1;i<=n;++i)
            s[i]=b[i] ;

         slen=n ;

         fw.init() ;

         int hv = fw.hashVal(1,n) ;

         for(int i=1;i<=2*n;++i)
            s[i]=a[i] ;

         slen=2*n ;

         fw.init() ;

         bool pos=false ;

         for(int i=1;i<=n;++i)
         {
             if(fw.hashVal(i,i+n-1)==hv)
                pos=true ;
         }

         if(!pos)
         {
             Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
             continue ;
         }

         bool equ=true ;

         for(int i=1;i<=n;++i)
            if(a[i]!=b[i])
               equ=false ;


         if(n==2)
         {
             if(equ and k%2==0)
                Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else if(equ==false and k%2==1)
                Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else
                Output<<"Case #"<<tt<<": "<<"NO"<<endl ;

             continue ;
         }

         if(k>0)
         {
             if(k==1 and equ)
                 Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
             else
                 Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
         }
         else
         {
             if(equ)
                 Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else
                 Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
         }

    }

    Input.close() ;

    Output.close() ;
/**/
    return 0 ;
}


///  ac code of facebook hackercup 
///  double hash with double mod

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<iterator>
#include<climits>
#include<functional>
#include<iomanip>
using namespace std;
#define   MP             make_pair
#define   PB             push_back
#define   nn             '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   ALL(vec)       vec.begin(),vec.end()
#define   int            long long
#define   ll             long long
#define   pii            pair<int,int>

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int INF=1LL*1000*1000*1000*1000*1000*1000+7LL, INF2=(1LL<<62) ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

int test , a[N] , b[N] ;

int n , m , k , one , two ;

const ll MAX_N = 1e6+10, mod1 = 2e9+63, mod2 = MOD , base1 = 1e9+21, base2 = 1e9+181;
int s[MAX_N];  // 1-indexed
ll pw1[MAX_N], pw2[MAX_N], slen;

void pw_calc() {
    pw1[0] = pw2[0] = 1;
    for(int i = 1; i < MAX_N; i++) {
        pw1[i] = (pw1[i-1] * base1) % mod1;
        pw2[i] = (pw2[i-1] * base2) % mod2;
    }
}

struct Hash {
    ll h1[MAX_N], h2[MAX_N];

    void init() {
        h1[0] = h2[0] = 0;
        for(int i = 1; i <= slen; i++) {
            h1[i] = (h1[i-1] * base1 + s[i]) % mod1;
            h2[i] = (h2[i-1] * base2 + s[i]) % mod2;
        }
    }

    inline pii hashVal(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod1;
        if(hsh1 < 0) hsh1 += mod1;
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod2;
        if(hsh2 < 0) hsh2 += mod2;
        return {hsh1,hsh2};
    }

    inline ll hashOne(int l, int r) {
        ll hsh1 = (h1[r] - h1[l-1] * pw1[r-l+1]) % mod1;
        if(hsh1 < 0) hsh1 += mod1;
        return hsh1;
    }

    inline ll hashTwo(int l, int r) {
        ll hsh2 = (h2[r] - h2[l-1] * pw2[r-l+1]) % mod2;
        if(hsh2 < 0) hsh2 += mod2;
        return hsh2;
    }
} fw;

bool same(pii a,pii b)
{
    return a.first==b.first and a.second==b.second ;
}

int32_t main()
{
    IOS

    pw_calc() ;

    fstream Input, Output ;

    Input.open("E:/online judge/Facebook/input.txt", ios::in);

    if (!Input)
    {
        cout << "No such file" ;
    }

    Output.open("E:/online judge/Facebook/output.txt", ios::out) ;

    Input>>test ;

    for(int tt=1;tt<=test;++tt)
    {
         int n , k ;

         Input>>n>>k ;

         for(int i=0;i<=2*n+5;++i)
            a[i]=b[i]=0 ;

         for(int i=1;i<=n;++i)
            Input>>a[i] ;

         for(int i=1;i<=n;++i)
            Input>>b[i] ;

         for(int i=n+1;i<=2*n;++i)
            a[i]=a[i-n] , b[i]=b[i-n] ;

         for(int i=1;i<=n;++i)
            s[i]=b[i] ;

         slen=n ;

         fw.init() ;

         pii hv = fw.hashVal(1,n) ;

         for(int i=1;i<=2*n;++i)
            s[i]=a[i] ;

         slen=2*n ;

         fw.init() ;

         bool pos=false ;

         for(int i=1;i<=n;++i)
         {
             if(same(fw.hashVal(i,i+n-1),hv))
                pos=true ;
         }

         if(!pos)
         {
             Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
             continue ;
         }

         bool equ=true ;

         for(int i=1;i<=n;++i)
            if(a[i]!=b[i])
               equ=false ;

         bool alleq=true ;

         if(!equ)
            alleq=false ;

         for(int i=1;i<n;++i)
            if(a[i]!=a[i+1])
              alleq=false ;

         if(alleq)
         {
             Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             continue ;
         }

         if(n==2)
         {
             if(equ and k%2==0)
                Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else if(equ==false and k%2==1)
                Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else
                Output<<"Case #"<<tt<<": "<<"NO"<<endl ;

             continue ;
         }

         if(k>0)
         {
             if(k==1 and equ)
                 Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
             else
                 Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
         }
         else
         {
             if(equ)
                 Output<<"Case #"<<tt<<": "<<"YES"<<endl ;
             else
                 Output<<"Case #"<<tt<<": "<<"NO"<<endl ;
         }

    }

    Input.close() ;

    Output.close() ;
/**/
    return 0 ;
}

/// tree hashing ... 
///https://codeforces.com/problemset/problem/1800/G

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
#define   MP             make_pair
#define   PB             push_back
#define   EB             emplace_back
#define   nn             '\n'
#define   endl           '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   all(vec)       vec.begin(),vec.end()
#define   int            long long
#define   pii            pair<int,int>
#define   pdd            pair<double,double>
#define   ff             first
#define   ss             second

using namespace std ;

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int oo=1LL*1000*1000*1000*1000*1000*1000+7LL ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

vector<int> bas = {181, 197,233,281,293};
vector<int> mod = {114802019,969832723,480566959,185749469,851370397};

bool sym[N];

array<int,5> hsh[N],dp[N];

vector<int>adj[N] , oadj[N] ;

void dfs(int nd,int lvl,int pa=0)
{
    map<vector<int>,int>cnt ;
    map<vector<int>,vector<int>>who ;
    for(int i=0; i<5; i++)
        dp[nd][i] = 1 ;
    for(int ch:adj[nd])
    {
        if(ch==pa)continue ;
        dfs(ch,lvl+1,nd) ;
        vector<int>vc ;
        for(int i=0; i<5; i++)
        {
            dp[nd][i]*=(hsh[lvl][i]+dp[ch][i]) ;
            dp[nd][i]%=mod[i] ;
            vc.PB(dp[ch][i]) ;
        }
        cnt[vc]++ ;
        who[vc].PB(ch) ;
    }
    int odd = 0 ;
    for(auto it:cnt){
        if(it.ss&1){
        ++odd ;
        for(int ch:who[it.ff])
            oadj[nd].PB(ch) ;
        }
    }
    sym[nd]=(bool)(odd<=1) ;
}

int32_t main()
{
    IOS

    for(int i=0; i<5; i++)
        hsh[0][i]=1 ;

    for(int i=1; i<N; i++)
        for(int j=0; j<5; j++)
            hsh[i][j]=bas[j]*hsh[i-1][j]%mod[j] ;

    int test, n  ;

    cin>>test ;

    while(test--)
    {
        cin>>n ;
        for(int i=1; i<n; ++i)
        {
            int u, v ;
            cin>>u>>v ;
            adj[v].PB(u), adj[u].PB(v) ;
        }
        dfs(1,1,0) ;
        int nd = 1 ;
        while(oadj[nd].size() and sym[1])
        {
            if(oadj[nd].size()==0)break ;
            if(oadj[nd].size()>1)sym[1] = 0 ;
            int ch = oadj[nd].back() ;
            sym[1] = sym[ch] ;
            nd = ch ;
        }
        for(int i=1; i<=n; i++)
            adj[i].clear() , oadj[i].clear() ;
        cout<<(sym[1]?"YES":"NO")<<endl ;
    }

    return 0 ;
}