NOIP提高組【JZOJ4805.】跟蹤

Description

Data Constraint

Solution

這道題其實很簡單。我們先将s視為樹根，周遊一下，求出每個點作以他為根的子樹的最大深度。然後我們将s到p和s到q的路徑上的點都走一遍，求出不包括目前點x不包括s到p和s到q的路徑上的點時以他為根的子樹的最大深度，求一遍答案即可。

代碼

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int first[maxn],last[maxn],next[maxn],v[maxn],deep[maxn],mx[maxn],fa[maxn];
int n,m,i,t,j,k,l,x,y,s,z,p,q,num,ln,fa2,fa1,ans,road[maxn],road1[maxn],num1;
bool bz[maxn];
void lian(int x,int y){
    last[++num]=y;next[num]=first[x];first[x]=num;
}
void bfs(){
    int i=,j=,t,k,l,x;
    v[]=s;bz[s]=true;deep[s]=;
    while (i<j){
        x=v[++i];
        for (t=first[x];t;t=next[t]){
            if (bz[last[t]]) continue;
            v[++j]=last[t],fa[v[j]]=x;deep[v[j]]=deep[x]+;bz[last[t]]=true;
        }
    }
    for (i=n;i>=;i--)
        mx[fa[v[i]]]=max(mx[fa[v[i]]]+,mx[v[i]]);
}
int main(){
//  freopen("track.in","r",stdin);freopen("track.out","w",stdout);
    scanf("%d%d%d%d",&n,&s,&p,&q);
    for (i=;i<n;i++)
        scanf("%d%d",&x,&y),lian(x,y),lian(y,x);    
    bfs();fa2=p;fa1=q;num=;memset(bz,,sizeof(bz));
    while (fa2!=s) bz[fa2]=true,road[++num]=fa2,fa2=fa[fa2];
    while (fa1!=s) bz[fa1]=true,road1[++num1]=fa1,fa1=fa[fa1];
    mx[s]=;
    bz[s]=true;mx[s]=;
    for (t=first[s];t;t=next[t])
        if (!bz[last[t]]) mx[s]=max(mx[last[t]]+,mx[s]);
    if (mx[s]>=min(deep[p],deep[q])) ans=*min(deep[p],deep[q]);
    else{
        t=mx[s]+min(deep[p],deep[q]);
        k=t/;
        ans=k*3;
        if (t%2) ans+=;
    }
    l=;x=deep[p],y=deep[q];
    for (i=num;i>=;i--){
        x-=;
        y--;z=road[i];mx[z]=;
        if (x<= || y<=){
            if (x!=-)ans=max(ans,l+);
            else ans=max(ans,l+);break;    
        }l+=;
        for (t=first[z];t;t=next[t])
            if (!bz[last[t]])mx[z]=max(mx[last[t]]+,mx[s]);
        if (mx[z]>=min(x,y)) ans=max(ans,l+*min(x,y));
        else{
            t=mx[z]+min(x,y);
            k=t/;k*=;
            if (t%2) k+=;
            ans=max(ans,l+k);
        }
    }
    l=;x=deep[p],y=deep[q];
    for (i=num1;i>=;i--){
        x--;
        y-=;z=road1[i];mx[z]=;
        if (x<= || y<=){
            if (y!=-)ans=max(ans,l+);
            else ans=max(ans,l+);break;    
        }l+=;
        for (t=first[z];t;t=next[t])
            if (!bz[last[t]])mx[z]=max(mx[last[t]]+,mx[s]);
        if (mx[z]>=min(x,y)) ans=max(ans,l+*min(x,y));
        else{
            t=mx[z]+min(x,y);
            k=t/;k*=;
            if (t%2) k+=;
            ans=max(ans,l+k);
        }
    }
    printf("%d\n",ans);
}