#1952. Everlasting Friends?

    ID: 1952 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2555来源:qoj.ac数据:公开样例图论并查集倍增

Everlasting Friends?

Everlasting Friends?

题目描述

标题: Everlasting Friends? - Problem - QOJ.ac

#14574. Everlasting Friends?

Statistics

The problem was used in the following contests:

This problem is prepared by rizynvu and sszcdjr .

等到一切有关这【】OI 的事情结束,所有的利益与竞争化为乌有,我们还会是朋友……吗?

题目描述

小 σ 有一张包含 n 个人,n−1 条朋友关系的关系网。保证在这个关系网中所有人连通,也就是说,将 n 个人视为点,n−1 条朋友关系视为边后该关系网为一棵树。

关系网是会变化的,毕竟没有永远的朋友。

小 σ 常常追忆过去,他想起过去的关系网是现在关系网按 1,2,3,…,n 顺序加入点后的重构树。

小 σ 常常幻想未来,他发现未来的关系网是现在关系网按 n,n−1,n−2,…,1 顺序加入点后的重构树。

小 σ 定义,对于某两张关系网而言,如果 {1,2,3,…,n} 的一个非空集合 S 在两张关系网上的导出子图均为一个连通块,则 S 为这两张关系网的不变朋友子集。

小 σ 想知道,过去的关系网与现在的关系网有多少不变朋友子集以及过去的关系网与未来的关系网有多少不变朋友子集。由于答案可能较大,你只需要输出答案对 998244353 取模后的值即可。


形式化题意

给定一棵 n 个点的树 T,定义 Tmax 为按 1,2,3,…,n 顺序加入点后的重构树,Tmin 为按 n,n−1,n−2,…,1 顺序加入点后的重构树,f(T1,T2) 为使得 S 在 T1,T2 上的导出子图均为连通块的 {1,2,3,…,n} 的非空子集 S 个数。求 f(Tmax,T) 与 f(Tmax,Tmin) 对 998244353 取模后的值。


按顺序 ord1,ord2,ord3,…,ordn 加入点构建重构树的具体流程为:

  1. 维护点集 S,按 i=1,2,3,…,n 依次遍历每个 p=ordi。
  2. 对于所有在原树上与 p 相邻且在 S 中的点 q,将 S 点集的导出子图中 q 所在连通块最晚加入 S 的点在重构树上与 p 连边。
  3. 将 p 加入点集 S。

输入格式

第一行两个正整数 tp,n,分别表示询问类型与点数。tp=1 时你需要输出过去的关系网与现在的关系网有多少不变朋友子集,tp=2 时你需要输出过去的关系网与未来的关系网有多少不变朋友子集。

接下来 n−1 行,每行两个正整数 ui,vi,表示一条朋友关系。保证在这个关系网中所有人连通。

输出格式

一行,输出一个非负整数,表示答案对 998244353 取模后的值。

样例

样例 1 输入

1 6
3 1
1 6
6 4
4 2
4 5

样例 1 输出

15

样例 2 输入

2 6
3 1
1 6
6 4
4 2
4 5

样例 2 输出

13

数据范围

子任务编号 n≤ tp= 特殊限制 分值 1 10 1 5 2 2000 15 3 2×105 树退化为一条链 5 4 树退化为菊花图 5 5 10 6 10 2 5 7 100 10 8 500 10 9 5000 10 10 2×105 树退化为一条链 5 11 树退化为菊花图 5 12 15

对于所有数据:1≤tp≤2,1≤n≤2×105,保证关系网中所有人连通。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 6
3 1
1 6
6 4
4 2
4 5
15

样例 2

2 6
3 1
1 6
6 4
4 2
4 5
13