文章目錄

• 題目描述
• 前言
• 解析
• 代碼
• thanks for reading！

題目描述

前言

全網(wǎng)唯一AC！！！
妙啊
而且還是完全自己想出來的做法
開心
（APIO還是沒白聽）

但是思路出來后代碼實現(xiàn)十分坎坷
建兩個圖分別dfs3次那個地方就算是寫不明白了
代碼能力需要加強

解析

定義數(shù)組dis：

dis[i]表示i在自己那棵樹上所能連出的最長簡單路徑

不難看出：
對于將兩棵樹上的邊x，y相連時
新的直徑要么是兩棵樹原來一棵的直徑，要么就是經(jīng)過了x和y
也就是：

max3（直徑A，直徑B，dis[x]+dis[y]+1)

通過對兩棵樹分別進行dfs，我們是可以預(yù)處理出兩棵樹的直徑和dis數(shù)組的
那么：

X=max（直徑A，直徑B）

就成了定值

那么我們現(xiàn)在考慮如何找出所有的x，y，使得二者相連的的貢獻大于X
也就是：

dis[x]+dis[y]>X

我們發(fā)現(xiàn)：
可以把A樹的dis降序排序一下
然后再枚舉B的dis值
這樣在A的dis序列中與B當(dāng)前的dis符合條件的點分布就是單調(diào)的
可以通過二分求解
假設(shè)對于B的dis1，A的dis序列的1-p的點i滿足：

dis1+disA[i]>X

那么通過dis1得到的貢獻之和就是

∑(disA[i]+dis1+1)(1<=i<=p)+X*(n-p)

把西格瑪拆開：

∑disA[i] (1<=i<=p)+(dis1+1)p+X(n-p)

前面的西格瑪可以用前綴和預(yù)處理處來
這樣我們就可以在二分求出p后O1求出dis1的貢獻了
總時間復(fù)雜度：
（n+m)logn
（從復(fù)雜度可以看出來，還可以在m<n時將兩棵樹交換以優(yōu)化復(fù)雜度，不過本題并不需要了）

代碼

#include<bits/stdc++.h> using namespace std; const int N=1e6+100; #define ll long long int n,m,root,mod;struct node{int to,nxt; }p[N*4]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; // printf("x=%d y=%d id=%d\n",x,y,cnt); } int fi2[N]; void addline2(int x,int y){p[++cnt]=(node){y,fi2[x]};fi2[x]=cnt; }int dis2A[N],disA[N],dis2B[N],disB[N]; int r=-1; int xa,ya,xb,yb; ll ans; void dfsA(int x,int f){ // printf("f=%d x=%d dis=%d\n",f,x,disA[x]);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to; // printf("id=%d to=%d\n",i,to);if(to==f) continue;disA[to]=disA[x]+1;if(r==-1||disA[r]<disA[to]) r=to;dfsA(to,x);} } void dfs2A(int x,int f){ // printf("f=%d x=%d dis=%d\n",f,x,disA[x]);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to; // printf("id=%d to=%d\n",i,to);if(to==f) continue;dis2A[to]=dis2A[x]+1;dfs2A(to,x);} } void dfsB(int x,int f){for(int i=fi2[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;disB[to]=disB[x]+1;if(r==-1||disB[r]<disB[to]) r=to;dfsB(to,x);} } void dfs2B(int x,int f){for(int i=fi2[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dis2B[to]=dis2B[x]+1;dfs2B(to,x);} }int X; void solve(){dfsA(1,0);xa=r;r=-1;memset(disA,0,sizeof(disA));dfsA(xa,0);ya=r; // for(int i=1;i<=n;i++) printf("i=%d dis=%d\n",i,disA[i]);dfs2A(ya,0);for(int i=1;i<=n;i++) disA[i]=max(disA[i],dis2A[i]);X=disA[xa]; // for(int i=1;i<=n;i++) printf("i=%d dis=%d\n",i,disA[i]);dfsB(1,0);xb=r;r=-1;memset(disB,0,sizeof(disB));dfsB(xb,0);yb=r;dfs2B(yb,0);for(int i=1;i<=m;i++) disB[i]=max(disB[i],dis2B[i]); // for(int i=1;i<=m;i++) printf("i=%d dis=%d\n",i,disB[i]);X=max(X,disB[xb]);// printf("%d %d %d %d X=%d\n",xa,ya,xb,yb,X); }bool cmp(int x,int y){return x>y;} ll sum[N]; void compute(){sort(disB+1,disB+m+1,cmp);for(int i=1;i<=m;i++){sum[i]=sum[i-1]+disB[i];}for(int i=1;i<=n;i++){int now=disA[i];int st=0,ed=m;while(st<ed){int mid=(st+ed+1)>>1;if(disB[mid]+now+1>=X) st=mid;else ed=mid-1;}ans+=(ll)sum[st]+(ll)st*now+st+(ll)(m-st)*X;} } int main(){memset(fi,-1,sizeof(fi));memset(fi2,-1,sizeof(fi2));int a,b,c,d;scanf("%d%d",&n,&m);for(int i=1;i<n;i++){scanf("%d%d",&a,&b);addline(a,b);addline(b,a);}for(int i=1;i<m;i++){scanf("%d%d",&c,&d);addline2(c,d);addline2(d,c);} // printf("dkesf=%d\n",p[0].to);solve();compute();printf("%lld",ans); } /* 3 5 1 2 1 3 1 2 1 3 3 4 4 5 */

thanks for reading！

總結(jié)

以上是生活随笔為你收集整理的树的合并（ybtoj-树上dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。