题目背景

警告：滥用本题评测者将被封号

We could have had it all. . . . . .

我们本该，拥有一切

Counting on a tree. . . . . .

何至于此，数数树上

Counting on a Tree（CoaT）即是本题的英文名称。

题目描述

Access Globe 最近正在玩一款战略游戏。在游戏中，他操控的角色是一名C 国士兵。他的任务就是服从指挥官的指令参加战斗，并在战斗中取胜。

C 国即将向D 国发动一场秘密袭击。作战计划是这样的：选择D 国的s 个城市，派出C 国战绩最高的s 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度 $d_idi ，$

C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市，派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市，以此类推（即派遣战绩第i高的士兵潜入所选择城市中危险程度第i 高的城市）。D 国有n 个城市，n - 1 条双向道路连接着这些城市，使得这些城市两两之间都可以互相到达。为了任务执行顺利，C 国选出的s 个城市中，任意两个所选的城市，都可以不经过未被选择的城市互相到达。

Access Globe 操控的士兵的战绩是第k 高，他希望能估计出最终自己潜入的城市的危险程度。Access Globe 假设C 国是以等概率选出任意满足条件的城市集合S ，他希望你帮他求出所有可能的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和。如果选择的城市不足k 个，那么Access Globe 不会被派出，这种情况下危险程度为0。

当然，你并不想帮他解决这个问题，你也不打算告诉他这个值除以998 244 353 的余数，你只打算告诉他这个值除以64,123 的余数。

输入输出格式

输入格式：

从文件coat.in 中读入数据。

第1 行包含3 个整数n、k、W，表示D 国城市的个数、Access Globe 所操控士兵潜入的城市战绩排名以及D 国的所有城市中最大的危险程度；

第2 行包含n 个1 到W 之间的整数 $d_1d1 ; d_2d2 ; ... d_ndn ，表示每个城市的危险程度；$

第3 行到第n + 1 行，每行两个整数 $x_ixi ; y_iyi ，表示D 国存在一条连接城市x_ixi 和城市y_iyi 的双向道路。$

输出格式：

输出到文件coat.out 中。输出一个整数，表示所有可行的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和除以64,123 的余数。

输入输出样例

输入样例#1：

5 3 32 1 1 2 31 22 31 41 5

输出样例#1：

输入样例#2：

10 2 32 1 1 3 1 2 3 3 1 31 22 32 42 52 65 71 88 91 10

输出样例#2：

说明

D 国地图如下，其中危险程度为d 的城市的形状是(d + 3) 边形。

以下是所有符合条件且选择的城市不少于3 个的方案：

• 选择城市1、2、3，Access Globe 的士兵潜入的城市危险程度为1；

• 选择城市1、2、3、4，Access Globe 的士兵潜入的城市危险程度为1；

• 选择城市1、2、3、5，Access Globe 的士兵潜入的城市危险程度为1；

• 选择城市1、2、3、4、5，Access Globe 的士兵潜入的城市危险程度为2；

• 选择城市1、2、4，Access Globe 的士兵潜入的城市危险程度为1；

• 选择城市1、2、5，Access Globe 的士兵潜入的城市危险程度为1；

• 选择城市1、2、4、5，Access Globe 的士兵潜入的城市危险程度为2；

• 选择城市1、4、5，Access Globe 的士兵潜入的城市危险程度为2；而在选择的城市少于3 时，Access Globe 的士兵潜入的城市危险程度均为0；

所以你应该输出(1 + 1 + 1 + 2 + 1 + 1 + 2 + 2) mod 64 123 = 11。

　　嗯...初看似乎是不可做题。只会链状的n^2*logn暴力qwq

　　好像正解是FFT... 弃疗的节奏。

　　然而有选手写了n^3暴力，竟然A掉了qaq 惊得下巴掉下来...

　　这种优雅的暴力就是考虑每个点对答案的贡献。我们枚举每个点，以该点为根进行树形dp。把键值大于该点的节点设为1，其余设为0，那么问题就转化成了求包含k个1的联通集合。

　　一开始只能想到n*k^2的转移方法，然而这样不就n^2*k^2了吗？好像跟题解说的不一样啊qwq

　　题解的方法是先从上到下更新，再用子节点更新父亲节点，很厉害的样子=-= （新技能get✔

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define KI 64123 6 #define LL long long 7 #define RI register int 8 using namespace std; 9 const int INF = 0x7ffffff ;10 const int N = 1666 + 10 ;11 12 inline int read() {13     int k = 0 , f = 1 ; char c = getchar() ;14     for( ; !isdigit(c) ; c = getchar())15       if(c == '-') f = -1 ;16     for( ; isdigit(c) ; c = getchar())17       k = k*10 + c-'0' ;18     return k*f ;19 }20 struct Edge {21     int to, nex ;22 }e[N<<1] ;23 int n, k, w, sdd, rr, ans = 0 ;  int v[N], head[N], siz[N], f[N][N] ; 24 inline void add_edge(int x,int y) {25     static int cnt = 0 ;26     e[++cnt].to = y, e[cnt].nex = head[x], head[x] = cnt ;27 }28 29 void dfs(int x,int fa,int *ff) {30     if(v[x] > v[rr] || (v[x] == v[rr] && x > rr)) {31         for(int i=1;i<=k;i++) f[x][i] = ff[i-1] ;32     } else for(int i=1;i<=k;i++) f[x][i] = ff[i] ;33     for(int i=head[x];i;i=e[i].nex) {34         int y = e[i].to ; if(y == fa) continue ;35         dfs(y,x,f[x]) ;36     }37     for(int i=1;i<=k;i++) ff[i] = (ff[i]+f[x][i])%KI ;38 }39 inline void solve(int r) {40     int tot = 1 ; rr = r ;41     for(int i=1;i<=n;i++) if(v[i] > v[r] || (v[i] == v[r] && i > r)) tot++ ;42     if(tot < k) return ;43     memset(f[r],0,sizeof(f[r])) ; f[r][1] = 1 ;44     for(int i=head[r];i;i=e[i].nex) {45         int y = e[i].to ;46         dfs(y,r,f[r]) ;47     }48     ans = (ans+v[r]*f[r][k])%KI ;49 }50 51 int main() {52     n = read(), k = read(), w = read() ;53     for(int i=1;i<=n;i++) v[i] = read() ;54     for(int i=1;i

　（好像最近做的省选题都要被分到思维题里面，好气哦qaq）

转载于:https://www.cnblogs.com/zub23333/p/8857263.html

你可能感兴趣的文章