免费自助建站平台系统,网站建设如何选择服务器,深圳趣网站建设,通用模板做的网站不收录文章目录题目描述前言解析代码thanks for reading#xff01;题目描述 前言
全网唯一AC#xff01;#xff01;#xff01; 妙啊 而且还是完全自己想出来的做法 开心 #xff08;APIO还是没白听#xff09;
但是思路出来后代码实现十分坎坷 建两个图分别dfs3次那个地方…
文章目录题目描述前言解析代码thanks for reading题目描述 前言
全网唯一AC 妙啊 而且还是完全自己想出来的做法 开心 APIO还是没白听
但是思路出来后代码实现十分坎坷 建两个图分别dfs3次那个地方就算是写不明白了 代码能力需要加强
解析
定义数组dis dis[i]表示i在自己那棵树上所能连出的最长简单路径 不难看出 对于将两棵树上的边xy相连时 新的直径要么是两棵树原来一棵的直径要么就是经过了x和y 也就是 max3直径A直径Bdis[x]dis[y]1) 通过对两棵树分别进行dfs我们是可以预处理出两棵树的直径和dis数组的 那么
Xmax直径A直径B就成了定值
那么我们现在考虑如何找出所有的xy使得二者相连的的贡献大于X 也就是 dis[x]dis[y]X 我们发现 可以把A树的dis降序排序一下 然后再枚举B的dis值 这样在A的dis序列中与B当前的dis符合条件的点分布就是单调的 可以通过二分求解 假设对于B的dis1A的dis序列的1-p的点i满足 dis1disA[i]X 那么通过dis1得到的贡献之和就是 ∑(disA[i]dis11)(1ip)X*(n-p) 把西格玛拆开 ∑disA[i] (1ip)(dis11)pX(n-p) 前面的西格玛可以用前缀和预处理处来 这样我们就可以在二分求出p后O1求出dis1的贡献了 总时间复杂度 nm)logn 从复杂度可以看出来还可以在mn时将两棵树交换以优化复杂度不过本题并不需要了
代码
#includebits/stdc.h
using namespace std;
const int N1e6100;
#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 ifi[x];~i;ip[i].nxt){int top[i].to;
// printf(id%d to%d\n,i,to);if(tof) continue;disA[to]disA[x]1;if(r-1||disA[r]disA[to]) rto;dfsA(to,x);}
}
void dfs2A(int x,int f){
// printf(f%d x%d dis%d\n,f,x,disA[x]);for(int ifi[x];~i;ip[i].nxt){int top[i].to;
// printf(id%d to%d\n,i,to);if(tof) continue;dis2A[to]dis2A[x]1;dfs2A(to,x);}
}
void dfsB(int x,int f){for(int ifi2[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;disB[to]disB[x]1;if(r-1||disB[r]disB[to]) rto;dfsB(to,x);}
}
void dfs2B(int x,int f){for(int ifi2[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dis2B[to]dis2B[x]1;dfs2B(to,x);}
}int X;
void solve(){dfsA(1,0);xar;r-1;memset(disA,0,sizeof(disA));dfsA(xa,0);yar;
// for(int i1;in;i) printf(i%d dis%d\n,i,disA[i]);dfs2A(ya,0);for(int i1;in;i) disA[i]max(disA[i],dis2A[i]);XdisA[xa];
// for(int i1;in;i) printf(i%d dis%d\n,i,disA[i]);dfsB(1,0);xbr;r-1;memset(disB,0,sizeof(disB));dfsB(xb,0);ybr;dfs2B(yb,0);for(int i1;im;i) disB[i]max(disB[i],dis2B[i]);
// for(int i1;im;i) printf(i%d dis%d\n,i,disB[i]);Xmax(X,disB[xb]);// printf(%d %d %d %d X%d\n,xa,ya,xb,yb,X);
}bool cmp(int x,int y){return xy;}
ll sum[N];
void compute(){sort(disB1,disBm1,cmp);for(int i1;im;i){sum[i]sum[i-1]disB[i];}for(int i1;in;i){int nowdisA[i];int st0,edm;while(sted){int mid(sted1)1;if(disB[mid]now1X) stmid;else edmid-1;}ans(ll)sum[st](ll)st*nowst(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 i1;in;i){scanf(%d%d,a,b);addline(a,b);addline(b,a);}for(int i1;im;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
