CF1060E Sergey and Subways 假的点分治
2024-09-30 09:11:05
题意:给出$N$个点的一棵树,现在将距离为$2$的点之间连一条边,求所有点对之间最短路的和,$N \leq 10^5$
一道树上乱搞题搞得我点分治调了一个小时$QAQ$
点分治中唯一需要注意的是:统计答案时因为长度为奇数的路线除二后要向上取整,所以要在计算时加上路径长度为奇数的路径数量
点分治都是模板题,会一个就全会了$qwq$
#include<bits/stdc++.h> #define MAXN 200010 #define int long long using namespace std; struct Edge{ int end , upEd; }Ed[MAXN << ]; long long head[MAXN] , size[MAXN] , N , minSize , minDir , nowSize , cntEd; long long ans; bool vis[MAXN]; inline void addEd(int a , int b){ Ed[++cntEd].end = b; Ed[cntEd].upEd = head[a]; head[a] = cntEd; } //求当前子树大小 void getNowSize(int dir){ vis[dir] = ; nowSize++; for(int i = head[dir] ; i ; i = Ed[i].upEd) if(!vis[Ed[i].end]) getNowSize(Ed[i].end); vis[dir] = ; } //求重心 void getZX(int dir){ vis[dir] = size[dir] = ; ; for(int i = head[dir] ; i ; i = Ed[i].upEd) if(!vis[Ed[i].end]){ getZX(Ed[i].end); size[dir] += size[Ed[i].end]; maxSize = max(maxSize , size[Ed[i].end]); } maxSize = max(maxSize , nowSize - size[dir]); if(maxSize < minSize){ minSize = maxSize; minDir = dir; } vis[dir] = ; } //算答案 pair < long long , long long > calAns(int dir , int dep){ vis[dir] = ; ans += dep + >> ; nowSize++; pair < ); for(int i = head[dir] ; i ; i = Ed[i].upEd) if(!vis[Ed[i].end]){ pair < ); q.first += t.first; q.second += t.second; } vis[dir] = ; return q; } void work(int dir){ nowSize = ; getNowSize(dir); minSize = nowSize; getZX(dir); , culJi = , culOu = ; vis[t] = ; nowSize = ; for(int i = head[t] ; i ; i = Ed[i].upEd) if(!vis[Ed[i].end]){ int k = nowSize; //注意答案统计! pair < ); ans += (sum * (nowSize - k) + t.first * k + t.second * culOu + culJi * (nowSize - k - t.second)) >> ; sum += t.first; culJi += t.second; culOu += nowSize - k - t.second; } for(int i = head[t] ; i ; i = Ed[i].upEd) if(!vis[Ed[i].end]) work(Ed[i].end); } signed main(){ ios::sync_with_stdio(); cin >> N; ; i < N ; i++){ int a , b; cin >> a >> b; addEd(a , b); addEd(b , a); } work(); cout << ans; ; }
最新文章
- OC基础--多态 及 三特性小练习
- 什么才是正确的javascript数组检测方式
- jQuery版本升级踩坑大全
- HDU 4707 DFS
- 大分享-hibernate,springmvc,easyui简要介绍
- 【Qt】学习笔记(一)
- POJ1679 The Unique MST(次小生成树)
- Android ListView标题置顶效果实现
- Hibernate逍遥游记-第12章 映射值类型集合-005对集合排序Map(<;order-by>;\<;sort>;)
- JS时间处理,获取天时分秒
- autorelease(转)
- MEAN 全栈开发 ——实现简单博客
- RAID知识总结[转]
- B. Menci 的序列
- 基于前后端分离的身份认证方式——JWT
- PHP从数组中找到指定元素的位置
- nginx代理学习
- RabbitMQ三种Exchange模式
- [C++] Function Template - optional parameter
- MySQL5.7主从同步--点位方式及GTID方式
热门文章
- html中用href 实现点击链接弹出文件下载对话框
- Docker第二章:docker基础1--镜像,容器&;仓库
- docker第一章:docker核心概念及centos6下安装
- ssms2014和ssms2016版本错误定位的区别
- Flume Channel Selector
- python 遇到的小坑
- Docker容器服务发现方案
- 洗礼灵魂,修炼python(26)--编程核心之“递归”
- IE push方法,最后一个参数后面不能跟";,";,否则报语法错误
- pkg-config 用法