给出一颗$N$个节点的树,现在我们**在原图中**每个不直接连边但是中间只间隔一个点的两个点之间连一条边. 比如**在原图中**$u$与$v$连边,$v$与$w$连边,但是$u$与$w$不连边,这时候我们就需要连一条$u$与$v$的边. 现在我们需要求出新图中每一个点对$(i,j)\ (1 \leq i \leq j \leq N)$的经过的边数和.
因为实在太菜了不会树形dp的只好用点分了……
（点分是个好东西所有树的题目都可以暴力艹过去）
首先，设原点对之间距离为$dis$，如果$dis$是奇数，那么新的距离为$(dis>>1)+1$，否则为$dis>>1$
我们考虑如何计算经过当前根节点的路径对答案的贡献
我们设已经dfs过的子树中有$cnt0$条长度为偶数的链，$dis0$这些链的每一条的长度除以二之和，同理$cnt1$和$dis1$表示长度为奇数的链的条数和每一条链的长度除以二加一的和
简单来讲$dis1$和$dis0$分别表示将原$dis$按上面的方法转化后的答案
然后考虑当前子树$v$，设$v$中的以上信息分别为，$cnt[0],cnt[1],dis[0],dis[1]$
然后就是路径的两两组合分别计入答案就是了
顺便注意因为两条奇数路径合起来变为偶数，所以相当于每一条路径的长度都要减一
然后别忘了加上子树单独的贡献
1 //minamoto 2 #include<bits/stdc++.h> 3 #define ll long long 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-‘0‘ 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch==‘-‘)&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=2e5+5; 19 int head[N],Next[N<<1],ver[N<<1],tot; 20 int cnt[2];ll dis[2],ans=0; 21 inline void add(int u,int v){ 22 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 23 } 24 int sz[N],son[N],size,vis[N],rt,n; 25 void findrt(int u,int fa){ 26 sz[u]=1,son[u]=0; 27 for(int i=head[u];i;i=Next[i]){ 28 int v=ver[i]; 29 if(vis[v]||v==fa) continue; 30 findrt(v,u),sz[u]+=sz[v],cmax(son[u],sz[v]); 31 } 32 cmax(son[u],size-sz[u]); 33 if(son[u]<son[rt]) rt=u; 34 } 35 void dfs(int u,int fa,int d){ 36 d&1?(++cnt[1],dis[1]+=((d>>1)+1)):(++cnt[0],dis[0]+=(d>>1)); 37 for(int i=head[u];i;i=Next[i]){ 38 int v=ver[i]; 39 if(v!=fa&&!vis[v]) dfs(v,u,d+1); 40 } 41 } 42 void getans(int u){ 43 int cnt0=0,cnt1=0;ll dis0=0,dis1=0; 44 for(int i=head[u];i;i=Next[i]){ 45 int v=ver[i]; 46 if(vis[v]) continue; 47 cnt[0]=cnt[1]=0,dis[0]=dis[1]=0; 48 dfs(v,u,1); 49 // ans+=dis[1]*dis1-cnt[1]*cnt1; 50 // ans+=dis[1]*dis0; 51 // ans+=dis[0]*dis1; 52 // ans+=dis[0]*dis0; 53 ans+=dis[1]*cnt1+dis1*cnt[1]-1ll*cnt1*cnt[1]; 54 ans+=dis[1]*cnt0+dis0*cnt[1]; 55 ans+=dis[0]*cnt1+dis1*cnt[0]; 56 ans+=dis[0]*cnt0+dis0*cnt[0]; 57 ans+=dis[1]+dis[0]; 58 cnt0+=cnt[0],cnt1+=cnt[1]; 59 dis0+=dis[0],dis1+=dis[1]; 60 } 61 } 62 void solve(int u){ 63 vis[u]=1,getans(u); 64 for(int i=head[u];i;i=Next[i]){ 65 int v=ver[i]; 66 if(vis[v]) continue; 67 size=sz[v],rt=0,findrt(v,u); 68 solve(rt); 69 } 70 } 71 int main(){ 72 // freopen("testdata.in","r",stdin); 73 n=read(); 74 for(int i=1,u,v;i<n;++i) 75 u=read(),v=read(),add(u,v),add(v,u); 76 son[rt=0]=n+1,size=n,findrt(1,0); 77 solve(rt); 78 printf("%I64d\n",ans); 79 return 0; 80 }
洛谷CF1060E Sergey and Subway（点分治）
原文：https://www.cnblogs.com/bztMinamoto/p/9767144.html