Tree_Sets.cpp

#include <bits/stdc++.h>
using namespace std;

// Time Complexity: O(n)
// Space Complexity: O(n)

using ll = long long;
const ll m = 998244353;

int n;
ll ans;
vector<ll> sub;
vector<vector<int>> adj;

void dfs(int x, int p) {
	ll val = 2;
	for(auto &y : adj[x]) {
		if(y == p) continue;
		dfs(y, x);
		sub[x] += sub[y];
		val *= (sub[y] + 1); val %= m;
	}
	ll up = (n - sub[x]);
	val *= (up + 1); val %= m;
	val = (val - n + m)%m; // rem size {0, 1} sets except yourself
	val = (val - (up*sub[x])%m + m)%m; // remove size {2} sets with upper
	// cout << "x - > " << x << " : val = " << val << "\n";
	ans += val; ans %= m;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);

	int tc; cin >> tc;
	while(tc--) {
		cin >> n;
		adj.assign(n, {});
		for(int i = 0; i < n-1; i++) {
			int u, v; cin >> u >> v;
			adj[u-1].push_back(v-1);
			adj[v-1].push_back(u-1);
		}
		ans = 0;
		sub.assign(n, 1);
		dfs(0, -1);
		cout << ans << "\n";
	}

	return 0;
}