一道淀粉质的题目。

先考虑最简单的算法，那便是对每个点都求一边。时间复杂度O(NM)

然后如果我们把每个点的结果对应一个高度，我们会发现。最优解是在这个对应高度形成的三维图像中的谷底（谷缝）

也就数说，对于一条链来说，他是一个开口向上的类似二次函数的一个图形。

具有类似单调性的一类性质。

在O(NM)的算法中，可以使用其剪枝。既是如果相邻的节点的答案要大于当前节点，那么我们就不向那个节点进行搜索。

为什么？ 如果相邻节点的答案小于当前点，那么说明，当前的最长链的两端都在相邻节点所确定的子树中。

所以我们往这颗子树中走就用可能是更优的。（随时取min）

为什么说是可能？因为这个最长链的位置可能改动。

---

对于这个二次函数图像，我们可以使用一个类似二分的方法，在log时间复杂度中找到最小值。

就是前文说的类似单调性一样的东西。

所以我们可以利用最长连所在的子树的重心进行检验。

因为重心的性质，我们就可以每次将问题至少缩小一半规模。

至于什么时候退出呢？

要么递归到底，要么子树重心的答案大于当前最优答案。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using std::min;using std::max;const int maxn=101000;const int inf=0x7fffffff;struct node{    int p;    int value;    int nxt;};node line[maxn<<1];int head[maxn],tail;int query[maxn][2];int vis[maxn],dis[maxn],size[maxn],f[maxn];int belong[maxn];int n,m,root,sum;int ans,where;int read(){    char c=getchar();    int res=0;    while(c>'9'||c<'0') c=getchar();    while(c>='0'&&c<='9')    {        res=(res<<1)+(res<<3)+c-'0';        c=getchar();    }    return res;}void add(int a,int b,int c){    line[++tail].p=b;    line[tail].value=c;    line[tail].nxt=head[a];    head[a]=tail;    return ;}void get_dis(int now,int fa,int Dis,int Belong){    dis[now]=Dis;    belong[now]=Belong;    for(int i=head[now];i;i=line[i].nxt)    {        int v=line[i].p;        if(v==fa)    continue;        get_dis(v,now,Dis+line[i].value,Belong);    }    return ;}void get_size(int now,int fa){    size[now]=1;    for(int i=head[now];i;i=line[i].nxt)    {        int v=line[i].p;        if(vis[v]||v==fa)   continue;        get_size(v,now);        size[now]+=size[v];    }    return ;}void get_hry(int now,int fa){    size[now]=1;f[now]=0;    for(int i=head[now];i;i=line[i].nxt)    {        int v=line[i].p;        if(vis[v]||v==fa)    continue;        get_hry(v,now);        size[now]+=size[v];        f[now]=max(f[now],size[v]);    }    f[now]=max(f[now],sum-size[now]);    if(f[now]
        
         Max)//    {//        ans=Max;//        where=root;//    }    for(int i=1;i<=m;i++)    {        int A=query[i][0],B=query[i][1];        if(dis[A]+dis[B]!=Max)  continue;        if(belong[A]==belong[B]&&(!Be||Be==belong[A]))            Be=belong[A];        else    if((!belong[A]||!belong[B])&&(!Be||Be==belong[A]+belong[B]))            Be=belong[A]+belong[B];        else    return ;    }    for(int i=head[root];i;i=line[i].nxt)        if(!vis[line[i].p]&&Be==belong[line[i].p])        {            solve(line[i].p);            return ;        }    return ;}int main(){    n=read();m=read();    for(int i=1,a,b,c;i