#P18897. [2026多校联测]重剪巡游录像

[2026多校联测]重剪巡游录像

题目描述

一场巡游表演结束后,摄影机器人留下了依次经过的路口编号,用来记录巡游路线。录像编辑员希望通过倒放某些片段调整这份记录;只有从同一个路口出发并回到该路口的片段才允许倒放。

巡游区域有 nn 个路口,编号为 1,2,…,n1,2,\ldots,n,路口之间有 n−1n-1 条双向道路,任意两个路口之间都存在道路相通,因此道路构成一棵树。

给出一份经过 mm 次道路通行的巡游记录

v0,v1,…,vm.v_0,v_1,\ldots,v_m.

记录中每两个相邻的路口之间必定有一条道路直接相连。允许反复经过同一个路口、同一条道路,保证这份记录至少访问每个路口一次。

编辑员可以进行有限次以下操作,也可以不操作:在当前记录中选择 0≤l<r≤m0\le l<r\le m,且满足 vl=vrv_l=v_r,将从位置 ll 到位置 rr 的整段记录逆序,其他位置不变。下一次操作仍以操作后的记录为准。

请统计:能通过这些操作得到多少份不同的记录,其字典序严格小于输入的原始记录?答案对 998244353998244353 取模。

所有记录的长度均为 m+1m+1。比较字典序时,找到第一个不同的位置,该位置路口编号更小的记录字典序更小。通过不同操作过程得到的同一份记录只计一次;原始记录不计入答案。

输入格式

第一行两个整数 n,mn,m。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示一条双向道路。

最后一行 m+1m+1 个整数 v0,v1,…,vmv_0,v_1,\ldots,v_m,表示原始巡游记录。

输出格式

输出一行一个整数,表示符合要求的不同记录数量对 998244353998244353 取模的结果。

样例 1 输入

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

样例 1 输出

1

样例 1 解释

将原始记录整体逆序,得到 [1,2,1,3,4,3,1][1,2,1,3,4,3,1]。原始记录的首尾均为 11,所以这是一次合法操作。

每条道路都恰好通行两次,路口 44 的访问必须包含在往返路口 33 的片段内部。因此只有上述两份不同记录,字典序更小的恰有一份。

样例 2 输入

3 7
2 1
2 3
2 3 2 1 2 1 2 3

样例 2 输出

2

样例 2 解释

每次从路口 22 离开,下一站只能为 11 或 33。前 33 次离开后都会返回路口 22,最后一次必须走向终点 33。前三次的下一站依次可以是 [1,1,3][1,1,3]、[1,3,1][1,3,1] 或 [3,1,1][3,1,1];相同目的地不可区分。原记录对应第三种,因此有 22 份记录比它小。

子任务

对于所有测试数据,保证:1≤n≤2000001\le n\le200000,0≤m≤2000000\le m\le200000;道路构成树;记录中的编号都在 11 至 nn 之间,相邻路口有道路直接相连,且记录访问所有路口。由此 n≤m+1n\le m+1。当 n=1n=1 时,必有 m=0m=0。

各子任务独立整组计分,通过该组全部测试点才能得到该组分数;各组无依赖关系。

子任务 分值 额外约束
1 20 m≤10m\le10
2 树为以路口 11 为中心的星形,且 v0=vm=1v_0=v_m=1
3 原始记录经过每条道路的次数均不超过 22(两个方向合计)
4 40 无额外约束