并不对劲的[Noi2008]道路设计

Time Limit: 20 Sec Memory Limit: 162 MB

Submit: 931 Solved: 509
[Submit][Status][Discuss]
Description

　　Z国坐落于遥远而又神奇的东方半岛上，在小Z的统治时代公路成为这里主要的交通手段。Z国共有n座城市，一些城市之间由双向的公路所连接。非常神奇的是Z国的每个城市所处的经度都不相同，并且最多只和一个位于它东边的城市直接通过公路相连。Z国的首都是Z国政治经济文化旅游的中心，每天都有成千上万的人从Z国的其他城市涌向首都。为了使Z国的交通更加便利顺畅，小Z决定在Z国的公路系统中确定若干条规划路线，将其中的公路全部改建为铁路。我们定义每条规划路线为一个长度大于1的城市序列，每个城市在该序列中最多出现一次，序列中相邻的城市之间由公路直接相连(待改建为铁路)。并且，每个城市最多只能出现在一条规划路线中，也就是说，任意两条规划路线不能有公共部分。当然在一般情况下是不可能将所有的公路修建为铁路的，因此从有些城市出发去往首都依然需要通过乘坐长途汽车，而长途汽车只往返于公路连接的相邻的城市之间，因此从某个城市出发可能需要不断地换乘长途汽车和火车才能到达首都。我们定义一个城市的“不便利值”为从它出发到首都需要乘坐的长途汽车的次数，而Z国的交通系统的“不便利值”为所有城市的不便利值的最大值，很明显首都的“不便利值”为0。小Z想知道如何确定规划路线修建铁路使得Z国的交通系统的“不便利值”最小，以及有多少种不同的规划路线的选择方案使得“不便利值”达到最小。当然方案总数可能非常大，小Z只关心这个天文数字modQ后的值。注意：规划路线1-2-3和规划路线3-2-1是等价的，即将一条规划路线翻转依然认为是等价的。两个方案不同当且仅当其中一个方案中存在一条规划路线不属于另一个方案。

Input

　　第一行包含三个正整数N、M、Q,其中N表示城市个数,M表示公路总数,N个城市从1~N编号,其中编号为1的是首都
。Q表示上文提到的设计路线的方法总数的模数。接下来M行,每行两个不同的正数ai、bi(1≤ai,bi≤N)表示有一条
公路连接城市ai和城市bi。输入数据保证一条公路只出现一次。

Output

　　包含两行。第一行为一个整数,表示最小的“不便利值”。第二行为一个整数,表示使“不便利值”达到最小时
不同的设计路线的方法总数modQ的值。如果某个城市无法到达首都,则输出两行-1。

Sample Input

Sample Output

1

10

********************************分割线********************************
由题目中的构图方式不难看出这是一棵树，题目中让做的事是将这棵树剖分，使得根到路径上轻链最多的点轻链最少。
树链剖分可以使根到路径上轻链最多的点轻链至多有log n个，也就是说最终答案肯定不超过log n。这样就可以从1开始枚举，直到有一个答案的方案数不为零。
将“点a到点b的路径上有多少条轻链”称为“点a到点b的距离”。
设dp(x,y,z)表示点y向它的子树连了x（1或2）条边，而且要想使根到所有点的距离符合要求，就必须让y的子树中所有点到y的距离不超过z。

现在假设要求出dp(0/1/2,u,dep)，已经算到了u的第p个儿子v，而且dp(0/1/2,v,dep)和dp(0/1/2,v,dep-1)已经求出。

设tmp1=dp(0,v,dep)+dp(1,v,dep)（这是u有连重链到v的情况），tmp2=dp(0,v,dep-1)+dp(1,v,dep-1)+dp(2,v,dep-1)（这是u没有重链到v的情况）。

当u到子树有两条边时，两条边中的一条可能是到v的，也可能不是。

当u到子树有一条边时，这一条边可能是到v的，也可能不是。

当u没有边到子树时，肯定没有边到v。

这样就能得出转移方程了，并不对劲的人表示代码里有，并不打算写在这里。

需要注意的是，dp的初值是1，而且有可能出现mod q之后恰巧为零的情况，所以取模时如果结果为0，要改成Q。

只有不能构成一棵树时要输出-1。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<iomanip>

#include<cstdlib>

#define maxn 100010

#define maxm maxn*2

#define ll long long

using namespace std;

ll n,fir[maxn],nxt[maxm],v[maxm],cnt,m,p;

ll dp[][maxn][],f[maxn],son[maxn];

bool vis[maxn][];

ll read(){

    ll x=,f=;

    char ch=getchar();

    while(isdigit(ch)== && ch!='-')ch=getchar();

    if(ch=='-')f=-;

    while(isdigit(ch))x=x*+ch-'',ch=getchar();

    return x*f;

}

ll log2(ll x){

    for(ll tmp=,i=;;tmp<<=,i++){

        if(tmp*>x||tmp>=x)return i;

    }

}

void addedge(ll u1,ll v1){v[cnt]=v1,nxt[cnt]=fir[u1],fir[u1]=cnt++;}

ll getf(ll u){return f[u]<?u:(f[u]=getf(f[u]));}

void add(ll u,ll v){

    ll fu=getf(u),fv=getf(v);

    if(fu==fv)return;

    if(fu>fv)swap(fu,fv);

    f[fu]+=f[fv];

    f[fv]=fu;

}

ll mod(ll x){

    return (x%p== && x!=)?p:x%p;

}

void solve(ll u,ll dep){

    if(vis[u][dep])return;

    vis[u][dep]=;

    for(ll k=fir[u];k!=-;k=nxt[k]){

        ll vv=v[k];

        if(vv!=f[u]){

            f[vv]=u;

            solve(vv,dep);solve(vv,dep-);

            ll x=dp[][vv][dep]+dp[][vv][dep],//One road to tree vv.

            y=dp[][vv][dep-]+dp[][vv][dep-]+dp[][vv][dep-];//No roads to tree vv.

            x=mod(x),y=mod(y);

            dp[][u][dep]=mod(dp[][u][dep]*y+dp[][u][dep]*x);

            dp[][u][dep]=mod(dp[][u][dep]*y+dp[][u][dep]*x);

            dp[][u][dep]=mod(dp[][u][dep]*y);

        }

    }

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    n=read(),m=read(),p=read();

    memset(f,-,sizeof(f));

    memset(fir,-,sizeof(fir));

    for(ll i=;i<=m;i++){

        ll x=read(),y=read();

        addedge(x,y);

        addedge(y,x);

        add(x,y);

    }

    if(f[]!=-n)cout<<-<<endl<<-;

    else{

        memset(f,-,sizeof(f));

        ll lim=log2(n);

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

            for(ll j=;j<=lim;j++){

                dp[][i][j]=;dp[][i][j]=dp[][i][j]=;

            }

        }

        for(ll i=;i<=lim;i++){

            solve(,i);

            if(dp[][][i]!= || dp[][][i]!= || dp[][][i]!=){

                cout<<i<<endl<<(dp[][][i]%p+dp[][][i]%p+dp[][][i]%p)%p;

                break;

            }

        }

    }

    return ;

}

/*

5 4 100

1 2

4 5

1 3

4 1

*/

巴特西

并不对劲的[Noi2008]道路设计

最新文章

热门文章