1. 题目

传送门= ̄ω ̄=
题意,给你一棵无根树,再给你一些点对。你现在可以使树上某一条边的长度变为0,求给出的点对之间的路径中最长的那条路径最短为多长。
数据范围30W

2. 题解

我太菜了,还要看题解才会

其实主要思路就是:
首先求出所有点对之间的路径长度,设l[i]为第i个点对之间的路径长度。然后二分答案ans,找到l[i]中所有大于ans的,也就是找到对于当前的ans不符合要求而必须要使其中某条边变为0的路径,然后将这些路径上的所有的边的标记都+1,最后枚举每条边,如果这条边上的标记等于l[i]中大于ans的l[i]的个数,那么说明这条边是所有的不符合要求的路径的公共边,然后就判断能否通过使这条边的长度变为0而让所有不符合条件的路径都符合条件(路径长度都小于等于ans),如果可以的话就说明当前的ans是可取的。然而如果所有的公共边都枚举完了而还没出先一条公共边能让所有路径长度都小于等于ans的话就说明当前这个ans不可取。

具体做法:
对于点对u,v,求它们之间的路径长度可以先求出它们的lca,然后设dis[i]表示点i到根节点的路径长度,那么u,v之间的路径长度等于$dis[u]+dis[v]-2×dis[lca]$
然后我们将l[i]求出来,二分答案的上界定为l[i]中的最大值,下界定为0。
二分答案的check函数中,我们找出所有长度大于ans的路径(设这样的路径条数为cnt),将这条路径上的所有边的标记都+1,这里可以用数剖,但是慢了,还是用树上差分快一些。然后找出被标记了cnt次的边,判断如果把这条边长度变为0能否使最长的那条路径的长度小于等于ans,如果可以则表示这个ans符合条件,是个可行的方案。如果所有的被标记了cnt次的边中没有一条能变为0后使得最长的那条路径长度小于等于ans则表明这个ans不符合条件,不可行。
最后二分后得到答案。

一些讨论:
1. 为什么只要对当前的ans找出长度大于ans的路径呢?因为别的路径小于等于ans,绝对是不会影响到ans可不可行的。
2. 为什么标记了cnt次的边才看变成0能否使ans符合条件呢?因为如果一条边没被标记cnt次,那么至少存在一条长度大于ans的路径不能减少长度从而导致至少有一条路径不符合条件,所以不必讨论标记次数少于cnt的边。
3. 为什么只要看最长的路径能否被减少到小于等于ans呢?因为我们只会减少公共边,所以所有不符合条件的路径的长度都会减少相同的值,最长的边一定还是最长的边。
4. 怎么标记一条路径?其实只要标记这条路径上的所有的点,然后对于一条边是否标记了cnt次,只要看这条边的两个端点是否都被标记了cnt次就行了。

代码:

#include <bits/stdc++.h>
#define NS (300005)
#define LGS (20)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int lca,l,u,v;}Q[NS];
struct graph
{
    int head[NS],nxt[NS<<1],to[NS<<1],d[NS<<1],cnt;
    graph(){memset(head,-1,sizeof(head)),cnt=0;}
    void add(int a,int b,int c)
    {
        nxt[cnt]=head[a],to[cnt]=b,d[cnt]=c,head[a]=cnt++;
    }
}G1,G2;
int n,m,fa[NS],pre[NS][LGS+1],dep[NS],dis[NS],val[NS],cal[NS];
bool cmp(query a,query b){return a.l<b.l;}
void init(int a)
{
    pre[a][0]=fa[a],dep[a]=dep[fa[a]]+1;
    for(int i=1;i<=LGS;i++)pre[a][i]=pre[pre[a][i-1]][i-1];
    for(int i=G1.head[a];i!=-1;i=G1.nxt[i])
        if(G1.to[i]!=fa[a])
        {
            dis[G1.to[i]]=dis[a]+G1.d[i],fa[G1.to[i]]=a;
            G2.add(a,G1.to[i],G1.d[i]),init(G1.to[i]);
        }
}
int get_lca(int a,int b)
{
    if(dep[a]>dep[b])swap(a,b);
    for(int i=LGS;i>=0;i--)if(dep[pre[b][i]]>=dep[a])b=pre[b][i];
    if(a==b)return a;
    for(int i=LGS;i>=0;i--)if(pre[a][i]!=pre[b][i])a=pre[a][i],b=pre[b][i];
    return pre[a][0];
}
void calc(int a)
{
    cal[a]=val[a];
    for(int i=G2.head[a];i!=-1;i=G2.nxt[i])calc(G2.to[i]),cal[a]+=cal[G2.to[i]];
}
bool check(int k)
{
    memset(val,0,sizeof(val));
    query p;p.l=k;
    int ub=(int)(upper_bound(Q+1,Q+1+m,p,cmp)-Q);
    if(ub>m)return 1;
    for(int i=ub;i<=m;i++)
    {
        val[Q[i].u]++,val[Q[i].v]++,val[Q[i].lca]--;
        if(fa[Q[i].lca])val[fa[Q[i].lca]]--;
    }
    calc(1);
    for(int i=1;i<=n;i++)if(cal[i]>=m-ub+1)
        for(int j=G2.head[i];j!=-1;j=G2.nxt[j])if(cal[G2.to[j]]>=m-ub+1)
            if(Q[m].l-G2.d[j]<=k)return 1;
    return 0;
}
int main()
{
    IN(n),IN(m);
    for(int i=1,a,b,c;i<n;i++)IN(a),IN(b),IN(c),G1.add(a,b,c),G1.add(b,a,c);
    init(1);
    for(int i=1;i<=m;i++)
    {
        IN(Q[i].u),IN(Q[i].v),Q[i].lca=get_lca(Q[i].u,Q[i].v);
        Q[i].l=dis[Q[i].u]+dis[Q[i].v]-(dis[Q[i].lca]<<1);
    }
    sort(Q+1,Q+1+m,cmp);
    int l=0,r=Q[m].l,mid;
    while(l<r)if(mid=(l+r)>>1,check(mid))r=mid;else l=mid+1;
    printf("%d\n",l);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *