分析:
听说正解是FFT+线段树合并,然而我并不会...
我们来思考其他的方法。
我们要求的是连通块第k大的和
对于某一个连通块,对答案的贡献=val(Rank.K)
我们不好直接算出每个连通块的Rank.K是多少
但我们可以枚举一个limit for 1->w ,Σ(val(Rank.K)>=lim的连通块的个数)就等于答案
为什么呢,因为这样一个连通块就被统计了val(Rank.K)次。
剩下的进行树形DP,设dp[i][j]为以i为根的子树,选出j个权值>=limit的点的方案数。
那么最后统计答案的时候便是Σ(dp[i][j])(K<=j<=size(i))
复杂度N^3其实是不对的,但是卡一卡常数还是过得去的
代码:
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register int
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll long long
#define inf (1<<29)
#define maxn 2000
#define add(x,y) e[++cnt].v=y,e[cnt].next=head[x],head[x]=cnt
using namespace std;
int n,m,cnt,w;
int ss[maxn],isn[maxn],head[maxn];
ll lim,ans;
ll val[maxn],dp[maxn][maxn],sz[maxn];
//dp[i][j] 在以i为根的子树,选择了j个权值大于等于lim的点的方案数
const ll mo=;
struct E{
int v,next;
}e[maxn<<]; inline int read()
{
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
inline int MO(int x,int v){x+=v;return x>=mo?x-mo:x;} void dfs(int u,int fa)
{
sz[u]=(val[u]>=lim)?:;
dp[u][sz[u]]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
per(ii,sz[u],)
if(dp[u][ii])
per(j,sz[v],)
if(dp[v][j])dp[u][ii+j]=MO(dp[u][ii+j],(dp[u][ii]*dp[v][j])%mo);
sz[u]+=sz[v];
}
rep(i,m,sz[u]) ans=MO(ans,dp[u][i]);
} int main()
{
n=read(),m=read(),w=read();
rep(i,,n) val[i]=read(),ss[val[i]]++;
for(RG i=,u,v;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
per(i,w,) ss[i]+=ss[i+];
rep(i,,w)
{
if(ss[i]<m) break;
memset(dp,,sizeof(dp));lim=i;
dfs(,);
}
cout<<ans;
return ;
}
秘密袭击 [BZOJ5250] [树形DP]的更多相关文章
-
[JZOJ4272] [NOIP2015模拟10.28B组] 序章-弗兰德的秘密 解题报告(树形DP)
Description 背景介绍弗兰德,我不知道这个地方对我意味着什么.这里是一切开始的地方.3年前,还是个什么都没见过的少年,来到弗兰德的树下,走进了封闭的密室,扭动的封尘已久机关,在石板上知道了这 ...
-
[BZOJ5250][九省联考2018]秘密袭击(DP)
5250: [2018多省省队联测]秘密袭击 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 3 Solved: 0[Submit][Status][D ...
-
【BZOJ5250】[九省联考2018]秘密袭击(动态规划)
[BZOJ5250][九省联考2018]秘密袭击(动态规划) 题面 BZOJ 洛谷 给定一棵树,求其所有联通块的权值第\(k\)大的和. 题解 整个\(O(nk(n-k))\)的暴力剪剪枝就给过了.. ...
-
P4365 [九省联考2018]秘密袭击coat
$ \color{#0066ff}{ 题目描述 }$ Access Globe 最近正在玩一款战略游戏.在游戏中,他操控的角色是一名C 国士 兵.他的任务就是服从指挥官的指令参加战斗,并在战斗中取胜. ...
-
Vijos p1770 大内密探 树形DP+计数
4天终于做出来了,没错我就是这么蒟蒻.教训还是很多的. 建议大家以后编树形DP不要用记忆化搜索,回溯转移状态个人感觉更有条理性. 大神题解传送门 by iwtwiioi 我的题解大家可以看注释&quo ...
-
BZOJ_2068_[Poi2004]SZP_树形DP
BZOJ_2068_[Poi2004]SZP_树形DP Description Byteotian *情报局 (BIA) 雇佣了许多特工. 他们每个人的工作就是监视另一名特工. Byteasar 国 ...
-
[九省联考2018]秘密袭击coat
[九省联考2018]秘密袭击coat 研究半天题解啊... 全网几乎唯一的官方做法的题解:链接 别的都是暴力.... 要是n=3333暴力就完了. 一.问题转化 每个联通块第k大的数,直观统计的话,会 ...
-
[loj2546][JSOI2018]潜入行动(树形DP)
题目描述 外星人又双叒叕要攻打地球了,外星母舰已经向地球航行!这一次,JYY 已经联系好了黄金舰队,打算联合所有 JSOIer 抵御外星人的进攻. 在黄金舰队就位之前,JYY 打算事先了解外星人的进攻 ...
-
poj3417 LCA + 树形dp
Network Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 4478 Accepted: 1292 Descripti ...
随机推荐
-
Ajax异步调用Controller的Return JsonResult生成下拉列表
@using System.Web.Optimization; @{ Layout = null; } <!DOCTYPE html> <html> <head> ...
-
python爬虫技术的选择
p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Helvetica } span.s1 { } 本篇文章不是入门帖,需要对python和爬虫领 ...
-
uva11025 The broken pedometer
6741870 ksq2013 UVA 11205 Accepted 60 C++11 5.3.0 1002 2016-08-04 14:25:22 题目大意如下:给定n个LED灯串,每个灯串由p ...
-
JMeter学习-008-JMeter 后置处理器实例之 - 正则表达式提取器(一)概述及简单实例
上文我们讲述了如何对 HTTP请求 的响应数据进行断言,以判断响应是否符合我们的预期,敬请参阅:JMeter学习-007-JMeter 断言实例之一 - 响应断言 那么我们如何获取 HTTP请求 响应 ...
-
windows openssl
1.安装Perl 下载 ActivePerl-5.20.2.2001-MSWin32-x64-298913,安装到 C:\Perl64\eg 运行 => cmd => cd C:\Perl ...
-
mapreduce实现全局排序
直接附代码,说明都在源码里了. package com.hadoop.totalsort; import java.io.IOException; import java.util.ArrayList ...
-
遍历HashMap的最佳方式
public static void printMap(Map mp) { Iterator it = mp.entrySet().iterator(); while (it.hasNext()) { ...
-
ELK学习笔记之ELK搜集OpenStack节点日志
模板来自网络,模板请不要直接复制,先放到notepad++内调整好格式,注意缩进 部署架构 控制节点作为日志服务器,存储所有 OpenStack 及其相关日志.Logstash 部署于所有节点,收集本 ...
-
ES学习
官方参考手册 https://www.elastic.co/guide/en/elasticsearch/reference/5.6/index.html https://www.elastic.co ...
-
linux系统快捷键
tab 补全命令 两次tab 列出所有以字符前缀开头的命令 ctrl A 把光标移到命令行开头 ctrl E 把光标移到命令行结尾 ctrl C 强制终止当前的命令 ct ...