当前位置: 首页 > news >正文

连锁网站开发江苏建设银行上班时间

连锁网站开发,江苏建设银行上班时间,建设公司网站标题,某高校门户网站开发案例Description 题库链接 给你 \(n\) 个节点的一棵树#xff0c;点分黑白。 \(q\) 组询问#xff0c;每次询问类似于“是否存在树中 \(x\) 个点的连通块恰有 \(y\) 个黑点”。 \(t\) 组数据。 \(1\leq t\leq 5,1\leq n\leq 5000,q\leq 10^5\) Solution 由于询问比较多#xff0… Description 题库链接 给你 \(n\) 个节点的一棵树点分黑白。 \(q\) 组询问每次询问类似于“是否存在树中 \(x\) 个点的连通块恰有 \(y\) 个黑点”。 \(t\) 组数据。 \(1\leq t\leq 5,1\leq n\leq 5000,q\leq 10^5\) Solution 由于询问比较多容易猜到一个结论就是 \(x\) 个点的连通块能取到黑点的个数一定是完整的一段区间。 就是只要 \(y\geq\) \(x\) 个点的连通块黑点个数的下界且 \(y\leq\) \(x\) 个点的连通块黑点个数的上界那么就满足题设条件。 具体证明大概就是在 \(x\) 个点的连通块中删去边界一个点再加上另一个不在连通块内的点这样黑点增量减量是不大于 \(1\) 的那么就一定能取到一整段区间内的数。 可以用 \(O(n^2)\) 的树上背包来预处理出这个上界下界。最后 \(O(1)\) 回答询问即可。 Code #include bits/stdc.h using namespace std; const int N 50005;int n, q, d[N], u, v, f[N][N], g[N][N], size[N]; struct tt {int to, next; }edge[N1]; int path[N], top;void dfs(int u, int fa) {if (d[u] 1) f[u][1] g[u][1] 1;else f[u][1] g[u][1] 0;size[u] 1; for (int i path[u], v; ~i; i edge[i].next)if ((v edge[i].to) ! fa) {dfs(v, u);for (int p size[u]; p; p--)for (int q size[v]; q; q--)f[u][pq] min(f[u][pq], f[u][p]f[v][q]),g[u][pq] max(g[u][pq], g[u][p]g[v][q]);size[u] size[v];}for (int i 1; i size[u]; i)f[0][i] min(f[0][i], f[u][i]), g[0][i] max(g[0][i], g[u][i]); } void add(int u, int v) {edge[top] (tt){v, path[u]}; path[u] top; } void work() {memset(path, top -1, sizeof(path));scanf(%d%d, n, q);for (int i 1; i n; i) scanf(%d%d, u, v), add(u, v), add(v, u);for (int i 1; i n; i) scanf(%d, d[i]);memset(f, 127/3, sizeof(f)), memset(g, 0, sizeof(g));dfs(1, 0);while (q--) {scanf(%d%d, u, v);if (f[0][u] v v g[0][u]) puts(YES);else puts(NO);}puts(); } int main() {int t; cin t; while (t--) work(); return 0; } 转载于:https://www.cnblogs.com/NaVi-Awson/p/8980588.html
http://wiki.neutronadmin.com/news/110985/

相关文章:

  • 笑话网站模板商标设计网上接单第一平台
  • 开鲁网站seo免费版网站建设岗位招聘
  • 网站结构怎么优化微信小程序云开发收费标准
  • 湖北响应式网站建设公司网站一定要备案吗
  • 郑州市城市建设管理局网站基础建设是什么意思
  • 广州网站建设推荐乐云seo最近房地产行情
  • 教育类网站设计阿里云服务器建设两个网站
  • 做寝室介绍网站东莞横沥做网站
  • 雁塔区建设局网站企业推广网
  • 网站如何做提现功能3g门户手机网
  • 林业门户网站建设如何备份网站数据
  • 网站打开速度网站自适应 如何做
  • 网站运营思路网站建设七个步骤
  • 有做网站设计吗wordpress分类目录绑定二级域名
  • 好的公文写作网站企业微信和个人微信的区别
  • 建设网站费用要进固定资产吗班级网站策划书
  • mip网站实例个人备案网站名
  • 网站建设策划书的主要内容公司网站开发的国内外研究现状
  • 网站建设 竞赛 方案长沙专业做网站公司哪家好
  • 网站后台小程序源码抓取工具
  • 集团网站设计网站建站公司公告
  • 注册网站用的信用卡如何网络推广优化
  • 营销型网站怎么建设网站开发标书
  • 广西兴业县建设局网站做网站的公司倒闭了
  • 海南网站建设服务广告策划ppt案例
  • 做电脑网站与手机上的一样吗多个网站备案
  • 企业网站开发培训1简述网站建设流程图
  • 网站上不去的原因网站怎么做第二个页面
  • 网站首页视频背景嘉兴港区规划建设门户网站
  • 网站设计流程软件网站运行费用一般多少