PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
You’re given a tree, each vertex of which must be colored red, blue, or green.
There should be at least one vertex of each color.
The score of a vertex is the sum of the closest vertices to it for each color.
Find the number of ways of coloring the vertices such that the sum of scores of all vertices is minimized.
EXPLANATION:
We know from the easy version that in an optimal solution, each non-leaf vertex has a score of 2 (meaning its neighbors contain both colors other than its own), and each leaf vertex has a score of 3 (meaning its neighbor has a different color, and some neighbor of that neighbor has the third color).
To count the number of colorings, we’ll use dynamic programming.
Let’s root the tree at some vertex, and try the standard tree DP: working with subtrees.
Suppose we’re trying to color vertex u, after having processed all its children.
Call a vertex fulfilled if the current coloring already gives it its minimum possible score.
Now, since we’ve colored all the vertices in the subtree of u other than u itself, observe that the only vertices that can still be unfulfilled are some children of u - anything at a further depth cannot be fulfilled by coloring u.
(There is one exception: leaf vertices that are at depth 2 from u. However, such a leaf vertex will be fulfilled if and only if its parent is also fulfilled, and this parent is a child of u so we can safely deal with only the children of u).
Further, if some child v of u is unfulfilled, note that the color of u will be uniquely determined by it (since u must fulfill v); which further means that all unfulfilled children of u must match in what they require.
This gives us a basic idea on what information needs to be stored to compute the answer:
- The color given to the current vertex.
- Whether the current vertex is fulfilled or not; and if not, which color it requires its parent to be.
With this, we obtain a dynamic programming solution that’s something like:
\text{dp}[u][c_1][c_2] is the number of ways to color everything in the subtree of u, such that u receives color c_1, and its parent must receive color c_2 (with c_2 = 0 if there’s no such restriction).
Here, we index the colors with values 1, 2, 3 for convenience.
This does work, but we can simplify it greatly using symmetry.
In particular, we see that for a fixed vertex u,
- \text{dp}[u][1][0] = \text{dp}[u][2][0] = \text{dp}[u][3][0], that is, no matter which color is chosen for u, the number of ways of coloring the subtree so that every vertex is fulfilled is the same.
- \text{dp}[u][x][x] = 0, since if u is unfulfilled and has color x, its parent must have a color other than x.
- All the \text{dp}[x][y] values for x \neq y and y \gt 0 are equal.
That is, coloring u red and requiring its parent to be green is no different from coloring u red and requiring its parent to be blue, and so on.
This means we only really need to store two values:
\text{dp}[u][0] is the number of ways to color the subtree of u such that everything is fulfilled.
\text{dp}[u][1] is the number of ways to color the subtree of u such that u isn’t fulfilled.
The first value will be three times the value of \text{dp}[u][1][0], while the second will be 6 times the value of \text{dp}[u][1][2].
Now, for transitions.
Suppose u is colored red, and unfulfilled.
For this to happen, blue and green cannot both appear among the children of u.
For now, suppose only green appears among the children of u (of course, red can appear too).
Then, for each child v of u,
- If v is fulfilled, there are \text{dp}[v][0] \cdot \frac{2}{3} configurations such that v is colored either red or green.
- If v is not fulfilled, there are \text{dp}[v][1] \cdot \frac{1}{6} configurations such that v is colored green, unfulfilled, and its parent must be red.
However, we must ensure that there exists at least one child colored green - so, we subtract out the number of configurations where every child is red.
So, there are
\prod_v \left(\text{dp}[v][0] \cdot \frac{2}{3} + \text{dp}[v][1] \cdot \frac{1}{6}\right) - \prod_v \left( \text{dp}[v][0] \cdot\frac{1}{3}\right)
ways of choosing the colorings of the descendants of u, such that u is colored red and its parent must be colored blue.
The product here is taken across all children v of u.
\text{dp}[u][1] of course equals 6 times this product, since we have three choices for the color of u and then two choices for what its parent should be.
Next, we want to compute \text{dp}[u][0].
The idea is quite similar again - let’s fix u to be red, and look at each child v of u.
- If v is fulfilled, it can take any color - so there are \text{dp}[v][0] options.
- If v isn’t fulfilled, there are \text{dp}[v][1] \cdot \frac{1}{3} options where v requires its parent to be red.
So, we obtain
\prod_v \left(\text{dp}[v][0] + \text{dp}[v][1] \cdot \frac{1}{3} \right)
colorings.
Multiply this by 3 to account for choosing u to be green or blue, too.
Again, not every coloring is valid, so we subtract out invalid ones.
Every coloring obtained in the computation of \text{dp}[u][1] is an invalid coloring, so \text{dp}[u][1] can be subtracted out.
Apart from that, colorings where u is the same color as all its children are also bad, and not included in \text{dp}[u][1] so we must subtract them out too.
Counting them is easy: for each child v there are \text{dp}[v][0] \cdot \frac{1}{3} colorings with v being the same color as u, so take their product (and multiply by 3 in the end, to account for the other two colors).
The final answer is just \text{dp}[root][0] since the root must be fulfilled once all is done.
This gives us a solution in \mathcal{O}(N) time.
There are a couple of details to take care of here — mainly, you might notice we ignored leaves entirely when computing the DP.
That’s not too hard to deal with though:
- First, ensure that the tree is rooted at a non-leaf (as in, a vertex with degree \gt 1).
Otherwise, whether u is satisfied or not will depend on things at depth 2 and that starts getting messy since our DP doesn’t handle that at all.
Rooting at a non-leaf sidesteps this entirely. - Second, if some child v of u is a leaf, you might need to take slightly different values from it.
This is left as an exercise to the reader
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
vector <ll> v[200005];
ll dp[200005][3];
ll mod=1000000007;
ll inv2,inv3;
void dfs(ll pos,ll par){
ll diff1=1;
ll ways=1;
ll same=1;
ll cnt;
for(auto it:v[pos]){
if(it!=par){
dfs(it,pos);
cnt=(((((dp[it][1]*inv2)%mod)+dp[it][0]+dp[it][2]*2)%mod)*inv3)%mod;
diff1*=cnt;diff1%=mod;
cnt=(((dp[it][0]*2+dp[it][1]+dp[it][2]*3)%mod)*inv3)%mod;
ways*=cnt;ways%=mod;
same*=(dp[it][2]*inv3)%mod;same%=mod;
}
}
dp[pos][1]=(6*(diff1-same+mod))%mod;
dp[pos][2]=(3*(ways-same+mod)-dp[pos][1]+mod)%mod;
if(v[pos].size()==1){
dp[pos][0]=3;
}
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll tt=1;
cin>>tt;
inv2=binpow(2,mod-2,mod);
inv3=binpow(3,mod-2,mod);
while(tt--){
ll n;
cin>>n;
for(int i=1;i<=n;i++){
v[i].clear();
dp[i][0]=dp[i][1]=dp[i][2]=0;
}
ll x,y;
for(int i=1;i<n;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
ll root=0;
for(int i=1;i<=n;i++){
if(v[i].size()>1){
root=i;
dfs(root,-1);
break;
}
}
cout<<dp[root][2]<<"\n";
}
return 0;
}
Tester's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
}inp;
using mint = static_modint<M>;
const int N = 2e5+5;
vi adj[N];
mint dp[N][3];
void dfs(int cur,int par){
if(adj[cur].size() == 1)return;
mint prod = 1;
mint tot = 1;
mint pr = 1;
int ch = 0;
for(auto x : adj[cur]){
if(x == par)continue;
dfs(x,cur);
mint sm = dp[x][0] + dp[x][1]/2 + dp[x][2]*2;
sm /= 3;
prod *= sm;
pr *= dp[x][2]/3;
mint sm1 = dp[x][0]*2 + dp[x][1] + dp[x][2]*3;
sm1 /= 3;
tot *= sm1;
ch++;
}
dp[cur][1] = (prod-pr)*2*3;
dp[cur][2] = tot*3 - dp[cur][1] - pr*3;
}
int parent[N];
int siz[N];
void make_set(int v) {
parent[v] = v;
siz[v] = 1;
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (siz[a] < siz[b])
swap(a, b);
parent[b] = a;
siz[a] += siz[b];
}
}
int smn = 0;
void solve()
{
int n;
// cin >> n;
n = inp.readInt(3,200000);
smn += n;
repin{
make_set(i);
}
inp.readEoln();
vi d(n);
repin{
adj[i].clear();
rep(j,0,3){
dp[i][j] = 0;
}
}
rep(i,0,n-1){
int u,v;
// cin >> u >> v;
u = inp.readInt(1,n);inp.readSpace();
v = inp.readInt(1,n);inp.readEoln();
assert(u != v);
u--;v--;
union_sets(u,v);
adj[u].pb(v);
adj[v].pb(u);
d[u]++;d[v]++;
}
assert(siz[find_set(0)] == n);
int r = 0;
repin{
if(d[i] > 1){r = i;break;}
}
repin{
if(d[i] == 1){
dp[i][0] = 3;
}
}
dfs(r,-1);
cout << dp[r][2].val() << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
// cin >> t;
t = inp.readInt(1,10000);
inp.readEoln();
while(t--)
solve();
inp.readEof();
assert(smn <= 200000);
return 0;
}