【CSP模拟赛】避难向导（倍增lca&树的直径）

耐力OIer，一天7篇博客

题目描述

“特大新闻，特大新闻！全国爆发了一种极其可怕的病毒，已经开始在各个城市中传播开来！全国陷入了巨大的危机！大量居民陷入恐慌，想要逃到其它城市以避难！经调查显示，该病毒来自于C 市的A 学校的一次非法的……” “哎。”你关上电视，叹了口气。作为A 学校的校长，你一天前为了保命，独自逃离了A 学校，抛弃了全校师生，包括那个曾经帮你计算并拆除道路的工程师。你良心受到了巨大的谴责，因此决定做出一些补救，回答一些逃难的人提出的询问。已知该国一共有n 个城市，并且1 号城市是首都。(n-1)条双向的公路连接这些城市，通过这些公路，任意两个城市之间存在且仅存在一条路径。每条公路有一个长度。如果一个城市只与一条公路相连，则称它为边境城市。该国政府有一个奇怪的规定：每个城市有一个封闭系数di，定义di为离这个城市最远的边境城市到这个城市的距离。市民们认为，一个城市的安全系数Si 和它的封闭系数有很重要的联系。a，b，c 是该国的幸运数字，所以大家公认一个城市的安全系数Si = (di + a) * b mod c。市民们一共会提出m 次询问。每个询问包含三个信息，xi，yi和qi。xi是询问者所在的城市编号。你要为这个询问者在xi 到yi 的必经之路上找出一个离xi 最近的避难城市，并且要求这个避难城市的安全系数大于等于qi。如果存在这样的城市（包含xi 和yi），则输出城市编号，否则输出一行包括一个数-1。

输入格式

第一行五个数：依次是n, m, a, b, c。接下来n-1 行描述公路的信息。每行三个数，前两个数代表这条公路连接的两个城市的编号，第三个数表示这条公路的长度。再接下来m 行，每行描述一个询问，包含三个数xi, yi 和qi。

输出格式

对于每个询问，输出一行包含一个整数，存在符合要求的城市则输出城市编号，不存在则输出-1。

输入样例

输出样例

提示

【样例解释】

从城市1到城市7的安全系数依次是：18,2,8,14,0,18,0。

【数据范围】

对于100%数据, n<=100000, m<=300000, 0<xi, yi<=n; a,b,c,qi<=1,000,000, c!=0;

分析

既然每个边境城市的度数为1，那么以任意点作为根（除边境城市），边境城市一定是叶子节点。

进而推出直径的两端一定是边境城市，不然就不是最长。

先求出直径，就可以计算出每个城市的安全系数（为什么O（n）的遍历我要用Dijkstra啊啊啊啊啊啊

因为不带修改，所以考虑用倍增来维护

只需要维护最大值和最小值就好了

对于每次询问x,y,q，先找出x，y的lca，然后分别在x到lca，lca到y中找

因为到x最近，所以在x到lca中找时尽量找深度大的，在lca到y中尽量找深度小的

先考虑x到lca

对dep[x]-dep[lca]二进制拆分，如果x到x向上2^k的祖先无解,即这中间的安全系数的最大值不满足要求，则x向上跳2^k步

如果有解，则lca向下跳到x的2^k的祖先，但此时dep[x]-dep[lca]=2^k，而k这一位我们已经拆分过了，所以不妨让x再向上跳一格，使dep[x]-dep[lca]=2^k-1

就可以继续拆分了。

再考虑lca到y

此时因为要深度最小，所以要判断lca到某个节点是否有解，还要多写一个函数

同样对dep[y]-dep[lca]二进制拆分，如果y到y向上2^k的祖先无解，则y向上跳2^k步

如果有解，因为要深度最小，还要判断y向上2^k的祖先是否有解，如果有，则仍然是y向上跳2^k步，如果没有，则lca向下跳到y的2^k的祖先，y向上跳一步

注意特判x，y为同一个点的情况

代码

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int LOG=;

const int maxn=;

struct node{int id;long long w;};

bool operator <(node a,node b){return a.w<b.w;}

int n,m,a,b,c,p1,p2,ecnt,info[maxn],nx[maxn<<],v[maxn<<],w[maxn<<];

long long d[][maxn],dep[maxn];int val[maxn],vis[maxn],fa[maxn][],mx[maxn][];

void add(int u1,int v1,int w1){nx[++ecnt]=info[u1];info[u1]=ecnt;v[ecnt]=v1;w[ecnt]=w1;}

void dfs1(int x,int f){if(dep[x]>=dep[p1])p1=x;for(int e=info[x];e;e=nx[e])if(v[e]!=f)dep[v[e]]=dep[x]+w[e],dfs1(v[e],x);}

void DIJK(int x,int k)

{

    memset(vis,,sizeof vis);priority_queue<node>q;q.push((node){x,});

    while(!q.empty())

    {

        node nw=q.top();q.pop();

        if(vis[nw.id])continue;vis[nw.id]=;d[k][nw.id]=nw.w;

        for(int e=info[nw.id];e;e=nx[e])if(d[k][v[e]]<d[k][nw.id]+w[e]&&!vis[v[e]])

        q.push((node){v[e],d[k][nw.id]+w[e]});

    }

}

void dfs(int x,int f)

{

    dep[x]=dep[fa[x][]=f]+;mx[x][]=max(val[x],val[f]);

    for(int i=;i<=LOG;i++)fa[x][i]=fa[fa[x][i-]][i-],mx[x][i]=max(mx[x][i-],mx[fa[x][i-]][i-]);

    for(int e=info[x];e;e=nx[e])if(v[e]!=f)dfs(v[e],x);

}

int Lca(int x,int y)

{

    if(dep[y]>dep[x])swap(x,y);

    for(int i=LOG;i>=;i--)if((dep[x]-dep[y])&(<<i))x=fa[x][i];if(x==y)return x=y;

    for(int i=LOG;i>=;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][]=fa[y][];

}

int getans(int x,int y)

{

    int ret=val[x];

    for(int i=LOG;i>=;i--)if(dep[fa[x][i]]>=dep[y])ret=max(ret,mx[x][i]),x=fa[x][i];

    return ret;

}

int find1(int x,int y,int q)

{

    if(getans(x,y)<q)return ;

    for(int i=;i>=;i--)if((dep[x]-dep[y])&(<<i))

    {

        if(mx[x][i]>=q)

        {

            y=fa[x][i];

            if(val[x]>=q)return x;

            x=fa[x][];

        }

        else x=fa[x][i];

    }

    return x;

}

int find2(int x,int y,int q)

{

    if(getans(x,y)<q)return ;

    for(int i=;i>=;i--)if((dep[x]-dep[y])&(<<i))

    {

        if(getans(fa[x][i],y)>=q)x=fa[x][i];

        else

        {

            y=fa[x][i];

            if(getans(fa[x][],y)>=q)x=fa[x][];

            else return x;

        }

    }

    return x;

}

int main()

{

    scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);

    for(int i=,u1,v1,w1;i<n;i++)scanf("%d%d%d",&u1,&v1,&w1),add(u1,v1,w1),add(v1,u1,w1);

    dfs1(,);p2=p1;p1=;memset(dep,,sizeof dep);dfs1(p2,);DIJK(p1,);DIJK(p2,);

    for(int i=;i<=n;i++)val[i]=1ll*(max(d[][i],d[][i])+a)*b%c;dfs(,);

    for(int i=,x,y,q,ret;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&q);

        int lca=Lca(x,y);ret=;

        if((ret=find1(x,lca,q))||(ret=find2(y,lca,q)))printf("%d\n",ret);

        else puts("-1");

    }

}

巴特西