LGP2680

7.15号,一天的时间耗在这个题上,ennn,反思总结.

1.玄学编译错误:一定要注意结构体的空间大小.

2.关于求树任意两点距离:用dis数组记录根节点到每一点距离,对于from,to

两点,用dis[from]+dis[to]-2*dis[LCA]即可求得树上两点距离,o(m)遍历便可,

今天用最短路dj求树上两点,o((n+m)*log(m))则不值.

3.板子一定要打稳,LCA今天调了很多次.

4.get求线段并的差分方法.

1.暴力

显然我们可以想到暴力枚举边权为零,再算出对m个计划的影响,求m个计划的最大时间中的最小值

要注意dis数组的使用,不要sb地用最短路,树上路线唯一确定.

2.正解.

1.对于最大值最小问题，我们会想到二分答案.将ans定义为能询问路径中合法存在的最长路径,我

们的任务就是将ans不断缩小.将询问路径中长度比ans大的找出来.可以这样理解,maxdis是我们

期望的最长最小,对那些比它长的路径我们希望通过虫洞减少,只有长的才对'最长路径'有影响.所以

我们找出最长的长出maxdis多长,看能不能通过虫洞消除,若能消除则一定有合法的更小值.若不能

则只能maxdis变长,对用虫洞去消长度的要求小一点.

2.如何用虫洞消?一定消比它长度的路径的交集路径的最大值.因为一定要影响整体,整体一个不合

法，maxdis就一定扩大，这就是为什么用最长的减最maxdis,因为我希望都合法,maxdis才缩小

3.如何去路径并?先考虑线段并,暴力染色看染色次数?线段树O(logn)维护?其实可以用差分.将线段

的l设置为1,r的后一位为-1,求一遍前缀和的过程中能得到每个点被覆盖次数.可理解为在线段区间

我们用1体现线段区间(区间两字用前缀和体现)染色,-1则体现消除影响(因为脱离区间).那么树上的

两点的距离可看做两点到LCA的两条线段,(num[LCA]-=2即这个意思).当覆盖次数等于加入线段个

数即表示它被所有区间覆盖,我们要求的虫洞即在这.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define e exit(0)
#define R register
#define ll long long
const int maxn=3*1e6+10;
long long n,m,cnt,l,r,deep,dfn[maxn],num[maxn],h[maxn],fa[maxn],dis[maxn],head[maxn],bz[maxn][24];
struct bian{
    ll to,next,v;
}len[maxn<<1];
struct kkk{
    ll from,to,lcaa,diss;
}ask[maxn<<1];
inline long long fd()
{
    long long s=1,t=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            s=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        t=t*10+c-'0';
        c=getchar();
    }
    return s*t;
}
void add(ll from,ll to,ll v)
{
    len[++cnt].v=v;
    len[cnt].to=to;
    len[cnt].next=head[from];
    head[from]=cnt;
}
void dfs(ll x)
{
    dfn[++deep]=x;
    for(R ll k=head[x];k;k=len[k].next)
    {
        ll to=len[k].to;
        if(!h[to])
        {
            h[to]=h[x]+1;
            fa[to]=x;
            dfs(to);
        }
    }
}
void makebz()
{
    h[1]=1,fa[1]=1;
    dfs(1);
    for(R ll i=1;i<=n;++i)
        bz[i][0]=fa[i];
    for(R ll j=1;j<=19;++j)
        for(R ll i=1;i<=n;++i)
            bz[i][j]=bz[bz[i][j-1]][j-1];    
}
long long LCA(ll x,ll y)
{
    if(h[x]<=h[y])
        swap(x,y);
    for(R ll k=19;k>=0;--k)
        if(h[bz[x][k]]>=h[y])
            x=bz[x][k];
    if(x==y)
        return x;
    for(R ll k=19;k>=0;--k)
        if(bz[x][k]!=bz[y][k])
            x=bz[x][k],y=bz[y][k];
    return fa[x];
}
void dfsdis(ll x,ll sum,ll fa)
{
    for(R ll k=head[x];k;k=len[k].next)
    {
        ll to=len[k].to,v=len[k].v;
        if(to==fa) continue;
        ll nowsum=sum+v;
        dis[to]=nowsum;
        dfsdis(to,nowsum,x);
    }
}
bool check(ll mid)
{
    ll cnt=0,maxdis=0;
    memset(num,0,sizeof(num));
    for(R ll i=1;i<=m;++i)
    {
        if(ask[i].diss>mid)
        {
            ll from=ask[i].from,to=ask[i].to,lca=ask[i].lcaa;
            ++num[from],++num[to],num[lca]-=2;
            maxdis=max(maxdis,ask[i].diss-mid);
            ++cnt;
        }
    }
    if(cnt==0)
        return true;
    for(R ll i=n;i>=1;--i)
        num[fa[dfn[i]]]+=num[dfn[i]];
    for(R ll i=2;i<=n;++i)
        if(num[i]==cnt&&dis[i]-dis[fa[i]]>=maxdis)
            return true;
    return false;
}
int main()
{
//    freopen("s.in","r",stdin);
//    freopen("s.out","w",stdout);
    n=fd(),m=fd();
    for(R ll i=1;i<n;++i)
    {
        ll from=fd(),to=fd(),v=fd();
        add(from,to,v),add(to,from,v);
        r+=v;
    }
    makebz();
    dfsdis(1,0,1);
    for(R ll i=1;i<=m;++i)
    {
        ll from=fd(),to=fd();
        ask[i].from=from,ask[i].to=to;
        ask[i].lcaa=LCA(from,to),ask[i].diss=dis[from]+dis[to]-2*dis[ask[i].lcaa];
    }
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}