题目描述

输入

输出

样例输入

4 2 1 3

1 2

2 3

3 4

样例输出

2

数据范围

解法

预处理出两个陌生人走到各个点的距离。

从石神处开始dfs，判断走到每一个点是否会被抓；

如果会，则计算答案，并给超级答案取最大值；

如果不会，继续走下去。

计算答案只需简单的运算，O(1)即可。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) int(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="track.in";

const char* fout="track.out";

const int inf=0x7fffffff;

const int maxn=200007,maxm=maxn*2;

int n,m1,m2,m3,i,j,k,tot,ans;

int fi[maxn],la[maxm],ne[maxm];

int dis[3][maxn];

void add_line(int a,int b){

    tot++;

    ne[tot]=fi[a];

    la[tot]=b;

    fi[a]=tot;

}

void getdis(int v,int from,int deep,int id){

    int i,j,k;

    dis[id][v]=deep;

    for (k=fi[v];k;k=ne[k]) if (la[k]!=from) getdis(la[k],v,deep+1,id);

}

void dfs(int v,int from,int time){

    int i,j,k=inf;

    /*if (v!=m1) {

        if (dis[1][v]/2<=dis[0][v]){

            if (dis[1][v]%2) k=min(k,2);

            else k=0;

        }

        if (dis[2][v]/2<=dis[0][v]){

            if (dis[2][v]%2) k=min(k,2);

            else k=0;

        }

        if (k!=inf){

            ans=max(time+k,ans);

            return ;

        }

    }*/

    if (v==m1 || dis[1][v]/2+dis[1][v]%2>dis[0][v] && dis[2][v]/2+dis[2][v]%2>dis[0][v])

        for (k=fi[v];k;k=ne[k])

            if (la[k]!=from){

                dfs(la[k],v,time+3);

            }

    ans=max(min(dis[1][v]/2*3+(dis[1][v]%2?2:0),dis[2][v]/2*3+(dis[2][v]%2?2:0)),ans);

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    scanf("%d%d%d%d",&n,&m1,&m2,&m3);

    for (i=1;i<n;i++){

        scanf("%d%d",&j,&k);

        add_line(j,k);

        add_line(k,j);

    }

    getdis(m1,0,0,0);

    getdis(m2,0,0,1);

    getdis(m3,0,0,2);

    dfs(m1,0,-2);

    printf("%d",ans);

    return 0;

}

启发

多出数据来调整细节。