[BZOJ 4326] [NOIP 2015] 운송 계획 (2 점 + dfs 순서 + 트 리 차이 점)

제목 설명
전송 문
해제
우선 최대 치 를 최소 화하 고 2 점 을 먼저 생각해 야 한다.모든 경로 에 필요 한 시간 을 미리 처리 할 수 있 습 니 다.관건 은 check 을 어떻게 하 는 거 죠?
알고리즘 은 매번 2 로 mid 를 나 눈 후에 모든 시간 > = mid 의 경로 에 표 시 를 한 다음 에 모든 변 을 매 거 합 니 다. 만약 에 이 변 에 표 시 된 수량 = 표 시 를 해 야 할 경로 의 수량 이 고 이 변 은 모든 만족 조건 에서 가장 큰 것 이 라면 이 변 을 잘 라 냅 니 다.그리고 이것 이 가능 한 지 아 닌 지 를 판단 하면 됩 니 다.그러나 이 시간의 복잡 도 는 O (logTmlogn) 로 끊 긴 다.
알고리즘 2. 우 리 는 알고리즘 1 을 바탕 으로 최적화 하 는 것 을 고려 합 니 다.알고리즘 1 의 병목 은 주로 check 할 때 O (mlogn) 이 고 조회 할 때 bit log 를 끼 웠 습 니 다.그러면 O (m) check 을 할 수 있 을까요?그럼요!방법 은 바로 -- 차이 점!여기 서 매우 자주 사용 하 는 나무의 차이 점 에 대한 생각 을 사 용 했 습 니 다. 점 x, y 설정 r = lca (x, y).x + 1, y + 1, r - 2 에 접미사 와 (x - > f [x]) 를 통계 합 니 다.이렇게 하면 모든 경 로 를 표시 한 후에 조회 하면 된다.
Po 의 코드 는 BZ 에서 얼마 빠 르 지 않 지만 UOJ 에서 알고리즘 2 가 훨씬 좋 은 것 을 발견 할 수 있다.(예 를 들 어 어 어 리 석 은 ATP 가 어 리 석 은 알고리즘 을 썼 더 니 카드 T 에 매 워 졌 다! - ATP:)
코드

#include
#include
#include
using namespace std;
#define N 300005
#define sz 19

int n,m,x,y,z,Max,dfs_clock,ans;
int tot,point[N],nxt[N*2],v[N*2],c[N*2];
int h[N],dis[N],val[N],num[N],tmp[N],f[N][sz+5];
struct hp{int x,y,lca,dis;}edge[N];

void addedge(int x,int y,int z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z;
}
void build(int x,int fa)
{
    num[++dfs_clock]=x;
    for (int i=1;iif ((h[x]-(1<1) break;
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for (int i=point[x];i;i=nxt[i])
        if (v[i]!=fa)
        {
            f[v[i]][0]=x;
            h[v[i]]=h[x]+1;dis[v[i]]=dis[x]+c[i];val[v[i]]=c[i];
            build(v[i],x);
        }
}
int lca(int x,int y)
{
    if (h[x]int k=h[x]-h[y];
    for (int i=0;iif ((1<if (x==y) return x;
    for (int i=sz-1;i>=0;--i)
        if (f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
bool check(int mid)
{
    int cnt=0,limit=0;memset(tmp,0,sizeof(tmp));
    for (int i=1;i<=m;++i)
        if (edge[i].dis>mid)
        {
            ++tmp[edge[i].x];++tmp[edge[i].y];tmp[edge[i].lca]-=2;
            limit=max(limit,edge[i].dis-mid);
            cnt++;
        }
    if (!cnt) return true;
    for (int i=n;i>1;--i) tmp[f[num[i]][0]]+=tmp[num[i]];
    for (int i=2;i<=n;++i)
        if (val[i]>=limit&&tmp[i]==cnt) return true;
    return false;
}
int find()
{
    int l=0,r=Max,mid,ans;
    while (l<=r)
    {
        mid=(l+r)>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;iscanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);Max+=z;
    }
    build(1,0);
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d",&edge[i].x,&edge[i].y);
        edge[i].lca=lca(edge[i].x,edge[i].y);
        edge[i].dis=dis[edge[i].x]+dis[edge[i].y]-dis[edge[i].lca]*2;
    }
    ans=find();
    printf("%d
",ans);
}

총결산
나무의 차이 점 에 대한 흔 한 사고: ① dfs 순서 의 시간 스탬프 를 이용 하여 한 점 을 두 점 으로 나 누고 매번 in + 1, out - 1 에 있 는 다음 에 bit 는 접두사 와 자기 동태 수정 과 서브 트 리 방문 횟수 를 통계 한다.하위 트 리 에 표 시 를 합 니 다.② 점 x, y 설정 r = lca (x, y).x + 1, y + 1, r - 2 에 접미사 와 (x - > f [x]) 를 통계 합 니 다.나무 사슬 에 표 시 를 하고 자 기 는 특정한 변 의 방문 횟수 를 조회 합 니 다.③ 점 x, y 설정 r = lca (x, y).x + 1, y + 1, r - 1, father [r] - 1 에 접미사 와 (x - > f [x]) 를 통계 합 니 다.나무 사슬 에 표 시 를 하고 자 기 는 특정한 점 의 방문 횟수 를 조회 합 니 다.