QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#946616#9805. Guide Mapji_114514TL 1ms5736kbC++203.7kb2025-03-22 00:35:302025-03-22 00:35:31

Judging History

This is the latest submission verdict.

  • [2025-03-22 00:35:31]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 5736kb
  • [2025-03-22 00:35:30]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long

using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());



struct DSU {
	std::vector<int> f, siz;

	DSU() {}
	DSU(int n) {
		init(n);
	}

	void init(int n) {
		f.resize(n);
		std::iota(f.begin(), f.end(), 0);
		siz.assign(n, 1);
	}

	int find(int x) {
		while (x != f[x]) {
			x = f[x] = f[f[x]];
		}
		return x;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}

	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return false;
		}
		siz[x] += siz[y];
		f[y] = x;
		return true;
	}

	int size(int x) {
		return siz[find(x)];
	}
};
const int N = 2e5 + 10, mod = 998244353;

ll qmi(ll a, ll k) {
	ll res = 1;
	while (k) {
		if (k & 1)res = res * a % mod;
		k >>= 1;
		a = a * a % mod;
	}
	return res;
}

int ln[N * 30], rn[N * 30], idx, cnt[N * 30], root[N];

void insert(int &u, int v, int l, int r, int x) {
	u = ++idx;
	cnt[u] = cnt[v] + 1, ln[u] = ln[v], rn[u] = rn[v];
	if (l == r)return;
	int mid = l + r >> 1;
	if (x > mid)insert(rn[u], rn[v], mid + 1, r, x);
	else insert(ln[u], ln[v], l, mid, x);
}

int query(int u, int v, int l, int r, int x, int y) {
	if (l > y || r < x)return 0;
	if (l >= x && r <= y)return cnt[u] - cnt[v];
	int mid = l + r >> 1;
	return query(ln[u], ln[v], l, mid, x, y) + query(rn[u], rn[v], mid + 1, r, x, y);
}

int n, rt, pa[N], dfn[N], sz[N], tot;
vector<int>e[N];
ll f[N], sum;
//就是个细节问题其实好说,自己的儿子比自己打也好说,不过好像是主席树写的有点问题说实话。
void dfs1(int u) {
	if (pa[u]) {
		e[u].erase(find(e[u].begin(), e[u].end(), pa[u]));
	}
	dfn[u] = ++tot, sz[u] = 1;
	insert(root[dfn[u]], root[dfn[u] - 1], 1, n, u);
	for (auto v : e[u]) {
		pa[v] = u;
		dfs1(v);
		sz[u] += sz[v];
	}
	f[u] = query(root[dfn[u] + sz[u] - 1], root[dfn[u] - 1], 1, n, u + 1, n);
	for (auto v : e[u])f[u] += f[v];//f[u] 做了个子树和
}
//换根将另外一边处理为对整棵树
//大概我们希望的就是以某个点为根,就是那个意思反正。
//比如一开始的f[root] 对答案的贡献大概就是 2^(f[root])
//然后我们需要的就是若干2的幂次和
void dfs2(int u) {
	sum = (sum + qmi(2, f[u])) % mod;
	//cout << u << ' ' << f[u] << "!\n";
	for (auto v : e[u]) {
		f[v] = f[u];
		//还挺简单的说实话。
		f[v] -= query(root[dfn[v] + sz[v] - 1], root[dfn[v] - 1], 1, n, u + 1, n);
		f[v] += query(root[dfn[v] - 1], root[dfn[rt] - 1], 1, n, v + 1, n) + query(root[n], root[dfn[v] + sz[v] - 1], 1, n, v + 1, n);
		dfs2(v);
	}
}
ll base, res;
//然后这个dfs就动态更新答案就好了,反正要处理好base啥的
//都套用一个主席树算了,懒得写了
//突然意识到一个严重的问题,我们query的其实是指数对吧。
void dfs3(int u) {
	res = (res + qmi(2, base) * sum) % mod;
	// cout << u << ' ' << base << ' ' << sum << ' ' << res << endl;
	for (auto v : e[u]) {
		//进入加入贡献
		ll temp = query(root[dfn[rt] + sz[rt]], root[dfn[rt] - 1], 1, n, v + 1, n);
		base += temp;
		dfs3(v);
		base -= temp;
	}
}

void solve()
{
	cin >> n;
	DSU dsu(n + 1);
	for (int i = 0; i < n - 2; i++) {
		int u, v; cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
		dsu.merge(u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!dsu.same(i, 1)) {
			rt = i;
			break;
		}
	}

	dfs1(1), dfs1(rt);

	dfs2(rt);
	if (sz[rt] == 1)res = (res + qmi(2, base)) % mod;
	base = f[1] - (sz[1] - 1);
	dfs3(1);


	//不要注意漏判孤立点
	cout << (res + mod) % mod << '\n';
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t = 1;
	while (t--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5736kb

input:

4
1 4
2 3

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5732kb

input:

2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Time Limit Exceeded

input:

4
1 2
1 3

output:


result: