5286. 【NOIP2017提高A组模拟8.16】花花的森林 (Standard IO)

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

Input

Output

Sample Input

3

1 2 3

1 2

1 3

2

1

Sample Output

6

9

6

Data Constraint

Hint

题解

我们考虑倒着做，即最开始是一个包含了 n 棵只有一个点的树的森林，然后不断加边，最后得到一棵完整的树。这样我们只需能够快速求出两棵树合并后得到新树的直径即可解决这个问题。

设合并的两棵树是 Ta 和 Tb，合并后形成的新树是 T。记 Ta 的直径的两端点为 ua 和va，Tb 的直径的两端点为 ub 和 vb，则 T 的直径的两端点一定 ∈ {ua, ub, va, vb}（由反证法不难证明）。这样我们只需维护每个块的直径及直径的两端点。在合并两个块时，我们只需暴力求出 4 个点对之间的路径长度，进行比较即可。

在这个过程中我们需要除以原来两块的直径。在模的意义下，除以一个数等价于乘以这个数的逆元。时间复杂度为O(n2)，期望得分 60 − 80 分。

我们考虑改进上面的做法，虽然有加边、删边操作，但事实上我们要求的点对之间的路

径长度都是原树上的路径。故我们可以通过对原树进行倍增预处理，每次在 O(logn) 的时间内求得点对间的最近公共祖先（lca），从而得到点对间的路径长度。

时间复杂度为O(nlogn)，期望得分 100 分。

代码

#include<cstdio>

#include<algorithm>

#include<vector>

#define ll long long

#define mo 1000000007

#define UP 20

#define N 100010

using namespace std;

struct point{

    long x,y;

    void make(long x,long y)

    {

        this->x=x;

        this->y=y;

    }

}root[N],b[N];

long n;

long fa[N][UP+1],dep[N],father[N],w[N],a[N],len[N],c[N],out[N];

void init()

{   long i,j;

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

        for(j=1;(1<<j)<=dep[i];j++)

            fa[i][j]=fa[fa[i][j-1]][j-1];

        father[i]=i;

        root[i].make(i,i);

        w[i]=a[i];

    }

}

long lca(long x,long y)

{   long up,xx=x,yy=y;

    if(dep[x]>dep[y])

        swap(x,y);

    for(up=UP;up>=0;up--)

        if(dep[y]-(1<<up)>=dep[x])

            y=fa[y][up];

    up=UP;

    while(x!=y){

        while(up>=0&&fa[x][up]==fa[y][up])

            up--;

        if(up<0)break;

        x=fa[x][up];

        y=fa[y][up];

        up--;

    }

    if(x==y)

        return len[xx]+len[yy]-2*len[x]+a[x];

    else

        return len[xx]+len[yy]-2*len[fa[x][0]]+a[fa[x][0]];

}

vector<long>map[N];

bool ok[N];

void dfs(long now)

{   long i,to,next;

    ok[now]=true;

    for(i=0;i<map[now].size();i++){

        to=map[now][i];

        if(!ok[to]){

            fa[to][0]=now;

            dep[to]=dep[now]+1;

            len[to]=a[to]+len[now];

            dfs(to);

        }

    }

}

long ksm(long a,long b)

{

    if(b>1)

        if(b&1)

            return (ll)ksm((ll)a*a%mo,b>>1)*a%mo;

        else

            return ksm((ll)a*a%mo,b>>1);

    else return a;

}

long cha(long x)

{

    return (father[x]==x)?x:father[x]=cha(father[x]);

}

void bin(long x,long y)

{

    father[cha(x)]=cha(y);

}

int main()

{   long i,xx,yy,r1,r2,r3,r4,w1,w2,w3,w4,maxx;

    long long ans=1;

    scanf("%ld",&n);

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

        scanf("%ld",&a[i]);

        ans=ans*a[i]%mo;

    }

    out[n]=ans;

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

        scanf("%ld%ld",&xx,&yy);

        b[i].make(xx,yy);

        map[xx].push_back(yy);

        map[yy].push_back(xx);

    }

    dfs(1);

    init();

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

        scanf("%ld",&c[i]);

    for(i=n-1;i>=1;i--){

        xx=cha(b[c[i]].x);

        yy=cha(b[c[i]].y);

        r1=root[cha(xx)].x;

        r2=root[cha(xx)].y;

        r3=root[cha(yy)].x;

        r4=root[cha(yy)].y;

        w1=lca(r1,r3);

        w2=lca(r1,r4);

        w3=lca(r2,r3);

        w4=lca(r2,r4);

        maxx=max(w1,max(w2,max(w3,max(w4,max(w[xx],w[yy])))));

        ans=ans*ksm(w[xx],mo-2)%mo*ksm(w[yy],mo-2)%mo*maxx%mo;

        bin(xx,yy);

        if(maxx==w1)

            root[cha(xx)].make(r1,r3);

        if(maxx==w2)

            root[cha(xx)].make(r1,r4);

        if(maxx==w3)

            root[cha(xx)].make(r2,r3);

        if(maxx==w4)

            root[cha(xx)].make(r2,r4);

        if(maxx==w[xx])

            root[cha(xx)].make(r1,r2);

        if(maxx==w[yy])

            root[cha(xx)].make(r3,r4);

        w[cha(xx)]=maxx;

        out[i]=ans;

    }

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

        printf("%ld\n",out[i]);

    return 0;

}

JZOJ 5286. 【NOIP2017提高A组模拟8.16】花花的森林 (Standard IO)的相关教程结束。