链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4545

题意：两个国家A，B，分别有N座城市和Q座城市(1 ≤ N, Q ≤ 4 × 10^4)，每个国家里的城市都是树形结构，每条边的权值都是1。现在要随机从两个国家中各选择一个城市来将两个国家连接起来，问连接起来的大国家里面的最长路的期望是多少。

思路：首先用树形DP找出所有点在本国里的能找到的最远距离，并且记录所有最远距离里的最长距离len。然后将B的所有最长路排序，并且对于A的每座城市，当A选择该座城市时，对于B的每座城市得到的最长路是max（len,dp_a[i][0]+dp_b[j][0]+1)，其中dp_a[i][0],dp_b[j][0]分别代表这两座城市能找到的最远距离。用二分找到满足dp_a[i][0]+dp_b[j][0]+1>len的位置，比这个位置大的长度就是dp_a[i][0]+dp_b[j][0]+1,起来的就是len。这样就可以求得期望了。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ctype.h>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define eps 1e-8
#define INF 0x7fffffff
#define maxn 40005
#define PI acos(-1.0)
#define seed 31//131,1313
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
int from_a[maxn],head_a[maxn],top_a;
int from_b[maxn],head_b[maxn],top_b;
double dp_a[maxn][2], dp_b[maxn][2];
double aa[maxn],bb[maxn];
struct Edge
{
    int v;
    int next;
} edge_a[maxn*2],edge_b[maxn*2];
void init()
{
    memset(head_a,-1,sizeof(head_a));
    memset(dp_a,0,sizeof(dp_a));
    memset(head_b,-1,sizeof(head_b));
    memset(dp_b,0,sizeof(dp_b));
    top_a=0;
    top_b=0;
}

void add_edge_a(int u,int v)
{
    edge_a[top_a].v=v;
    edge_a[top_a].next=head_a[u];
    head_a[u]=top_a++;
}
void add_edge_b(int u,int v)
{
    edge_b[top_b].v=v;
    edge_b[top_b].next=head_b[u];
    head_b[u]=top_b++;
}
void dfs_first(int u,int f,int head[],Edge edge[],int from[],double dp[][2])
{
    from[u]=u;
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)
            continue;
        dfs_first(v,u,head,edge,from,dp);
        if(dp[v][0]+1>dp[u][0])
        {
            from[u]=v;
            dp[u][1]=dp[u][0];
            dp[u][0]=dp[v][0]+1;
        }
        else if(dp[v][0]+1>dp[u][1])
            dp[u][1]=dp[v][0]+1;
    }
}
void dfs_second(int u,int f,int from[],double dp[][2],int head[],Edge edge[])
{
    if(u!=f)
        if(from[f]!=u)
        {
            if(dp[f][0]+1>dp[u][0])
            {
                from[u]=f;
                dp[u][1]=dp[u][0];
                dp[u][0]=dp[f][0]+1;
            }
            else if(dp[f][0]+1>dp[u][1])
                dp[u][1]=dp[f][0]+1;
        }
        else
        {
            if(dp[f][1]+1>dp[u][0])
            {
                from[u]=f;
                dp[u][1]=dp[u][0];
                dp[u][0]=dp[f][1]+1;
            }
            else if(dp[f][1]+1>dp[u][1])
                dp[u][1]=dp[f][1]+1;
        }
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)
            continue;
        dfs_second(v,u,from,dp,head,edge);
    }
}
int main()
{
    int T_a,T_b;
    while(~scanf("%d%d",&T_a,&T_b))
    {
        init();
        for(int i=1;i<=T_a-1;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge_a(u,v);
            add_edge_a(v,u);
        }
        dfs_first(1,1,head_a,edge_a,from_a,dp_a);
        dfs_second(1,1,from_a,dp_a,head_a,edge_a);
        for(int i=1;i<=T_b-1;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add_edge_b(u,v);
            add_edge_b(v,u);
        }
        dfs_first(1,1,head_b,edge_b,from_b,dp_b);
        dfs_second(1,1,from_b,dp_b,head_b,edge_b);
        double cc=0;
        double ans=0;
        for(int i=1;i<=T_a;i++)
        {
            if(dp_a[i][0]>cc)
                cc=dp_a[i][0];
        }
        for(int i=1;i<=T_b;i++)
        {
            bb[i]=dp_b[i][0];
            if(bb[i]>cc)
                cc=bb[i];
        }
        sort(bb+1,bb+T_b+1);
        double S[maxn];
        S[1]=bb[1];
        for(int i=2;i<=T_b;i++)
        {
            S[i]=S[i-1]+bb[i];
        }
        for(int i=1;i<=T_a;i++)
        {
            int pos=lower_bound(bb+1,bb+T_b+1,cc-dp_a[i][0]-1)-bb;
            ans+=(double)(pos-1)*cc;
            ans+=(T_b-pos+1)*(dp_a[i][0]+1)+S[T_b]-S[pos-1];
        }
        printf("%.3f\n",ans/((double)T_a*T_b)+eps);
    }
    return 0;
}

UvaLive 6534 Join two kingdoms 树形DP+二分