fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int MOD = 998244353;
  6. const int G = 3;
  7.  
  8. int modpow(ll a, ll e) {
  9.     ll r = 1 % MOD;
  10.     while (e) {
  11.         if (e & 1) r = r * a % MOD;
  12.         a = a * a % MOD;
  13.         e >>= 1;
  14.     }
  15.     return (int)r;
  16. }
  17.  
  18. void ntt(vector<int>& a, bool invert) {
  19.     int n = a.size();
  20.     for (int i = 1, j = 0; i < n; ++i) {
  21.         int bit = n >> 1;
  22.         for (; j & bit; bit >>= 1) j ^= bit;
  23.         j ^= bit;
  24.         if (i < j) swap(a[i], a[j]);
  25.     }
  26.     for (int len = 2; len <= n; len <<= 1) {
  27.         int wlen = modpow(G, (MOD - 1) / len);
  28.         if (invert) wlen = modpow(wlen, MOD - 2);
  29.         for (int i = 0; i < n; i += len) {
  30.             ll w = 1;
  31.             for (int j = 0; j < len/2; ++j) {
  32.                 int u = a[i + j];
  33.                 int v = (int)(a[i + j + len/2] * w % MOD);
  34.                 a[i + j] = u + v < MOD ? u + v : u + v - MOD;
  35.                 a[i + j + len/2] = u - v >= 0 ? u - v : u - v + MOD;
  36.                 w = w * wlen % MOD;
  37.             }
  38.         }
  39.     }
  40.     if (invert) {
  41.         int inv_n = modpow(n, MOD - 2);
  42.         for (int &x : a) x = (int)(1LL * x * inv_n % MOD);
  43.     }
  44. }
  45.  
  46. vector<int> conv(vector<int> a, vector<int> b) {
  47.     if (a.empty() || b.empty()) return {};
  48.     int n = 1;
  49.     while (n < (int)a.size() + (int)b.size() - 1) n <<= 1;
  50.     a.resize(n); b.resize(n);
  51.     ntt(a, false); ntt(b, false);
  52.     for (int i = 0; i < n; ++i) a[i] = (int)(1LL * a[i] * b[i] % MOD);
  53.     ntt(a, true);
  54.     a.resize((int)a.size() + (int)b.size() - 1);
  55.     return a;
  56. }
  57.  
  58. struct Poly4 {
  59.     vector<int> A, B, C, D;
  60. };
  61.  
  62. Poly4 merge_poly(const Poly4& L, const Poly4& R) {
  63.     Poly4 res;
  64.     res.A = conv(L.A, R.A);
  65.     res.B = conv(L.A, R.B);
  66.     auto tmp = conv(L.B, R.A);
  67.     if (res.B.size() < tmp.size()) res.B.resize(tmp.size(), 0);
  68.     for (int i = 0; i < (int)tmp.size(); ++i) {
  69.         res.B[i] += tmp[i];
  70.         if (res.B[i] >= MOD) res.B[i] -= MOD;
  71.     }
  72.  
  73.     res.C = conv(L.A, R.C);
  74.     tmp = conv(L.C, R.A);
  75.     if (res.C.size() < tmp.size()) res.C.resize(tmp.size(), 0);
  76.     for (int i = 0; i < (int)tmp.size(); ++i) {
  77.         res.C[i] += tmp[i];
  78.         if (res.C[i] >= MOD) res.C[i] -= MOD;
  79.     }
  80.  
  81.     res.D = conv(L.A, R.D);
  82.     tmp = conv(L.D, R.A);
  83.     if (res.D.size() < tmp.size()) res.D.resize(tmp.size(), 0);
  84.     for (int i = 0; i < (int)tmp.size(); ++i) {
  85.         res.D[i] += tmp[i];
  86.         if (res.D[i] >= MOD) res.D[i] -= MOD;
  87.     }
  88.     tmp = conv(L.B, R.C);
  89.     if (res.D.size() < tmp.size()) res.D.resize(tmp.size(), 0);
  90.     for (int i = 0; i < (int)tmp.size(); ++i) {
  91.         res.D[i] += tmp[i];
  92.         if (res.D[i] >= MOD) res.D[i] -= MOD;
  93.     }
  94.     tmp = conv(L.C, R.B);
  95.     if (res.D.size() < tmp.size()) res.D.resize(tmp.size(), 0);
  96.     for (int i = 0; i < (int)tmp.size(); ++i) {
  97.         res.D[i] += tmp[i];
  98.         if (res.D[i] >= MOD) res.D[i] -= MOD;
  99.     }
  100.     return res;
  101. }
  102.  
  103. Poly4 build_poly(const vector<int>& w, int l, int r) {
  104.     if (l == r) {
  105.         Poly4 p;
  106.         int x = w[l];
  107.         int x2 = (int)(1LL * x * x % MOD);
  108.         p.A = {1, x};
  109.         p.B = {0, 1};
  110.         p.C = {0, x2};
  111.         p.D = {0, x};
  112.         return p;
  113.     }
  114.     int mid = (l + r) >> 1;
  115.     Poly4 L = build_poly(w, l, mid);
  116.     Poly4 R = build_poly(w, mid + 1, r);
  117.     return merge_poly(L, R);
  118. }
  119.  
  120. struct DSU {
  121.     vector<int> p, sz;
  122.     DSU(int n=0){init(n);}
  123.     void init(int n){p.resize(n);sz.assign(n,1);iota(p.begin(),p.end(),0);}
  124.     int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
  125.     void unite(int a,int b){
  126.         a=find(a);b=find(b);
  127.         if(a==b) return;
  128.         if(sz[a]<sz[b]) swap(a,b);
  129.         p[b]=a; sz[a]+=sz[b];
  130.     }
  131. };
  132.  
  133. int main() {
  134.     ios::sync_with_stdio(false);
  135.     cin.tie(nullptr);
  136.  
  137.     int T;
  138.     cin >> T;
  139.  
  140.     // factorial
  141.     const int MAXN = 200000;
  142.     vector<int> fact(MAXN+5);
  143.     fact[0]=1;
  144.     for (int i=1;i<=MAXN;i++) fact[i]=(ll)fact[i-1]*i%MOD;
  145.  
  146.     while (T--) {
  147.         int n;
  148.         cin >> n;
  149.         vector<vector<int>> g(n+1);
  150.         for (int i=0;i<n-1;i++){
  151.             int u,v;cin>>u>>v;
  152.             g[u].push_back(v);
  153.             g[v].push_back(u);
  154.         }
  155.  
  156.         vector<int> parent(n+1,-1), order;
  157.         order.reserve(n);
  158.         order.push_back(1);
  159.         for(int i=0;i<(int)order.size();++i){
  160.             int u=order[i];
  161.             for(int v:g[u]) if(v!=parent[u]){
  162.                 parent[v]=u;
  163.                 order.push_back(v);
  164.             }
  165.         }
  166.         vector<int> sz(n+1,0);
  167.         for (int i=n-1;i>=0;--i){
  168.             int u=order[i];
  169.             int s=1;
  170.             for(int v:g[u]) if(v!=parent[u]) s+=sz[v];
  171.             sz[u]=s;
  172.         }
  173.  
  174.         DSU dsu(n+1);
  175.         for(int v=2;v<=n;v++){
  176.             if(sz[v]%2==1){
  177.                 dsu.unite(v,parent[v]);
  178.             }
  179.         }
  180.         // map components
  181.         unordered_map<int,int> id;
  182.         vector<int> comp_id(n+1);
  183.         int k=0;
  184.         vector<int> comp_size;
  185.         for(int i=1;i<=n;i++){
  186.             int r=dsu.find(i);
  187.             if(!id.count(r)){
  188.                 id[r]=k++;
  189.                 comp_size.push_back(0);
  190.             }
  191.             comp_id[i]=id[r];
  192.             comp_size[comp_id[i]]++;
  193.         }
  194.  
  195.         int rootComp = comp_id[1];
  196.         int kcomp = k;
  197.  
  198.         vector<int> w(kcomp);
  199.         for(int i=0;i<kcomp;i++) w[i]=comp_size[i];
  200.  
  201.         int wr = w[rootComp];
  202.         bool rootOdd = (wr%2==1);
  203.  
  204.         vector<int> E, O;
  205.         for(int i=0;i<kcomp;i++){
  206.             if(w[i]%2==0) E.push_back(i);
  207.             else O.push_back(i);
  208.         }
  209.  
  210.         vector<int> Oprime;
  211.         for(int v:O){
  212.             if(rootOdd && v==rootComp) continue;
  213.             Oprime.push_back(v);
  214.         }
  215.         int o = Oprime.size();
  216.  
  217.         ll P_O = 1;
  218.         ll sumInv_O = 0;
  219.         vector<int> w_odd;
  220.         w_odd.reserve(o);
  221.         for(int v:Oprime){
  222.             int wi=w[v];
  223.             w_odd.push_back(wi);
  224.             P_O = P_O * wi % MOD;
  225.             sumInv_O = (sumInv_O + modpow(wi, MOD-2)) % MOD;
  226.         }
  227.  
  228.         ll sumE = 0, invSumE = 0, P_E2 = 1;
  229.         for(int v:E){
  230.             if(v==rootComp && !rootOdd) continue;
  231.             int wi=w[v];
  232.             sumE = (sumE + wi) % MOD;
  233.             invSumE = (invSumE + modpow(wi, MOD-2)) % MOD;
  234.             P_E2 = P_E2 * wi % MOD * wi % MOD;
  235.         }
  236.         if (!rootOdd) sumE = (sumE + wr) % MOD;
  237.         ll baseSum = sumE;
  238.         if (rootOdd) baseSum = (baseSum + wr) % MOD;
  239.  
  240.         int Ecount = E.size();
  241.         if (rootOdd) Ecount = E.size();
  242.         else Ecount = E.size();
  243.  
  244.         ll N = n % MOD;
  245.  
  246.         vector<int> powN(o+1);
  247.         powN[0]=1;
  248.         for(int i=1;i<=o;i++) powN[i]=(ll)powN[i-1]*N%MOD;
  249.  
  250.         vector<int> A(o+1,0),B(o+1,0),C(o+1,0),D(o+1,0);
  251.         if(o==0){
  252.             A[0]=1; B[0]=C[0]=D[0]=0;
  253.         } else {
  254.             Poly4 poly = build_poly(w_odd,0,o-1);
  255.             A = poly.A; B = poly.B; C = poly.C; D = poly.D;
  256.         }
  257.  
  258.         ll constPart = (ll)wr * P_E2 % MOD * P_O % MOD;
  259.         ll ans = 0;
  260.  
  261.         if (o>=0) {
  262.             if ((E.size()==0 && rootOdd) || (E.size()==1 && !rootOdd)) {
  263.                 if (o==0) {
  264.                     ans = (ans + 1) % MOD;
  265.                 } else {
  266.                     ans = (ans + P_O * powN[o-1] % MOD * wr) % MOD;
  267.                 }
  268.             }
  269.         }
  270.  
  271.         for (int t=0; t<=o; ++t) {
  272.             int L = E.size() + t + (rootOdd ? 1 : 0);
  273.             if (L < 2) continue;
  274.             int U = o - t;
  275.  
  276.             if (U==0) {
  277.                 ll prodW = P_O;
  278.                 ll sumInvS = sumInv_O;
  279.                 ll term = (invSumE + sumInvS) % MOD;
  280.                 ll add = (ll)fact[L-2] * wr % MOD * P_E2 % MOD;
  281.                 add = add * prodW % MOD * prodW % MOD * term % MOD;
  282.                 ans = (ans + add) % MOD;
  283.             } else {
  284.                 ll term = 0;
  285.                 term = (term + invSumE * baseSum % MOD * A[t]) % MOD;
  286.                 term = (term + invSumE * C[t]) % MOD;
  287.                 term = (term + baseSum * B[t]) % MOD;
  288.                 term = (term + D[t]) % MOD;
  289.  
  290.                 ll add = constPart;
  291.                 add = add * fact[L-2] % MOD;
  292.                 add = add * powN[U-1] % MOD;
  293.                 add = add * term % MOD;
  294.                 ans = (ans + add) % MOD;
  295.             }
  296.         }
  297.  
  298.         cout << ans % MOD << "\n";
  299.     }
  300.     return 0;
  301. }
  302.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
4
1 2
1 3
3 4
5
1 2
1 3
1 4
1 5
5
1 2
2 3
1 4
4 5
6
1 2
2 3
2 4
2 6
5 6
11
2 10
6 8
1 6
3 7
5 11
5 8
5 9
4 7
6 7
2 6
stdout
copy 
4
1
16
8
2048
https://ideone.com/Dv21Wr
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

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!