题意:给出$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;
    ;
}

最新文章

  1. OC基础--多态 及 三特性小练习
  2. 什么才是正确的javascript数组检测方式
  3. jQuery版本升级踩坑大全
  4. HDU 4707 DFS
  5. 大分享-hibernate,springmvc,easyui简要介绍
  6. 【Qt】学习笔记(一)
  7. POJ1679 The Unique MST(次小生成树)
  8. Android ListView标题置顶效果实现
  9. Hibernate逍遥游记-第12章 映射值类型集合-005对集合排序Map(&lt;order-by&gt;\&lt;sort&gt;)
  10. JS时间处理,获取天时分秒
  11. autorelease(转)
  12. MEAN 全栈开发 ——实现简单博客
  13. RAID知识总结[转]
  14. B. Menci 的序列
  15. 基于前后端分离的身份认证方式——JWT
  16. PHP从数组中找到指定元素的位置
  17. nginx代理学习
  18. RabbitMQ三种Exchange模式
  19. [C++] Function Template - optional parameter
  20. MySQL5.7主从同步--点位方式及GTID方式

热门文章

  1. html中用href 实现点击链接弹出文件下载对话框
  2. Docker第二章:docker基础1--镜像,容器&amp;仓库
  3. docker第一章:docker核心概念及centos6下安装
  4. ssms2014和ssms2016版本错误定位的区别
  5. Flume Channel Selector
  6. python 遇到的小坑
  7. Docker容器服务发现方案
  8. 洗礼灵魂,修炼python(26)--编程核心之“递归”
  9. IE push方法,最后一个参数后面不能跟&quot;,&quot;,否则报语法错误
  10. pkg-config 用法