hdu 5739点双連通成分+乗算逆元超詳細説明

タイトルはこちらhttp://acm.hdu.edu.cn/showproblem.php?pid=5739 題意は大体以下の通りである:題目は大体1枚の無方向点に権無方向図を持っていると言っている.定義連通図の重み値は図中の各点の重みの積で、図の重み値はその含む各連通図の重み値の和で、ziをi点を削除した後の図の重み値にして、S=(1*z 1+2*z 2+3*z 3+......+n*zn);この問題はまるで毒性があって、大きなシミュレーションをしたような気がします.この問題の細部はとても多くて、十分に注意しなければなりません!!!まず,与えられた図はもともと連通していない可能性があるが,これは注意すべきこと,すなわち複数の連通サブ図を含む可能性があるので,別々に処理する.大まかな操作手順は、1、まず図の各連通サブ図の重み値を求める(このステップは、ステップ2でついでに実現することができる)、すなわち、削除点を考慮せずに各連通サブ図の重み値の大きさ、各サブ図の重み値の大きさを加算すると、削除点を考慮せずに元の図の重み値となり、Sumのために以下で直接参照させる.2、それから私達は一回tarjanを走って点を切ることを求めなければならなくて、もし点を切ることができないならば参考にしてくださいhttp://blog.csdn.net/Kamisama123/article/details/75007415(アクセス量/陰険を強引にブラシする)3、次に各点を列挙し、まずSum、すなわち図全体の重み値と、この点が存在する連通サブ図の重み値を減算し、これをssとし、そして、この点を削除したサブマップの重み値を加えるとZiになります.4、サブマップの重みを求める时、私达は点を2种类に分けます(割点と非割点)(1)点が非割点の时、私达ははっきり知っていて、この点を削除してもとの连通のサブマップに対して、何の影响もなくて、だから答えはサブマップの重み値がこの点を除いて、膜の意味の下で私达はその逆元に乗ります.逆元にならない場合は参考にしてくださいhttp://blog.csdn.net/Kamisama123/article/details/72823082 (2)この点が割点の場合、少し面倒になりますが、元のサブマップがより小さな図に複数割れてしまうので、tarjan走図のdfs順で、さらに図を1本の木に変えたと言えるので、ただ、この木は祖先や他の子や孫たちにつながっているかもしれませんが、遍歴の順番は木です.(ここではtarjanアルゴリズムを深く理解する必要がある)ので、各点uに対して1つのval[u]がuを表すサブツリーの重み積を求めると、この点uのすべてのvは、low[v]>=dfn[u]または(pre[u])があれば、この点を切断した後にvが分離することを示すので、これらの裂けたvalたval[v]の統計を加えてans 1とし、残りの重み値を算出し、つまりこの点の父親は,総じてこの連通サブマップの重み値の大きさをすべての割れたval[v](逆元)で割ってこのu点自体をans 2として割ってans 1とans 2とssを加算すればよい.最後にiに乗るのを忘れないでください.注意!!!もちろんこの問題にはいくつかの穴がありますが、この点uがルートノードである場合、ans 2は0になります.ルートノードの上には点がありませんが、ans 2は1になります.次に,連通サブマップの大きさが1の点しかない場合,この点を取り除くと0になり,特判する.
次はACのコードです.

#include
#include
#include
#include
#include
#define N 200005
#define dnt long long
#define mod 1000000007
#define del(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>son[N];
int T,n,m,num,head[N],a,b,belong[N],root[N];
int dfn[N],low[N],idc,cut[N],treecnt;
dnt aa[N],treeval[N],val[N];
struct Edge{
    int v,next;
};
Edge e[2*N];
void adde(int i,int j){
    e[++num].v=j;
    e[num].next=head[i];
    head[i]=num;
}
dnt ipow(dnt a,dnt b){
    dnt rt=1;
    for(dnt i=b,uni=a;i;uni=(uni*uni)%mod,i>>=1)
    if(i&1) rt=(rt*uni)%mod;
    return rt;
}
dnt inva(dnt a){
    return ipow(a,mod-2);
}
void init(){
    num=0;del(head,0);
    del(dfn,0);idc=0;
    del(cut,0);treecnt=0;
    del(root,0);
}
void tarjan(int u,int fa){
    dfn[u]=low[u]=++idc;
    belong[u]=treecnt;
    dnt an=aa[u];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(v,u);
            son[u].push_back(v);
            an=(an*val[v])%mod;
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])cut[u]++;
        }else low[u]=min(low[u],dfn[v]);
    }
    val[u]=an;
}
int main(){
//  freopen("date.in","r",stdin);
 // freopen("myans.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)son[i].clear();
        for(int i=1;i<=n;i++)
        scanf("%I64d",&aa[i]);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            adde(a,b);
            adde(b,a);
        }
        dnt tot=0,S=0;
        for(int i=1;i<=n;i++)
        if(!dfn[i])root[i]=1,cut[i]=-1,treecnt++,tarjan(i,-1),treeval[treecnt]=val[i];
        for(int i=1;i<=treecnt;i++)tot=(tot+treeval[i])%mod;
        for(int i=1;i<=n;i++){
            dnt temp=(tot-treeval[belong[i]]+mod)%mod;
            if(cut[i]<=0&&treeval[belong[i]]!=aa[i])temp=(temp+treeval[belong[i]]*inva(aa[i]))%mod;
            else{
                dnt ans1=0,ans2=1;
                for(int j=0;jint v=son[i][j];
                    if(low[v]>=dfn[i]){
                        ans1=(ans1+val[v])%mod;
                        ans2=(ans2*val[v])%mod;
                    }
                }
                dnt t=(treeval[belong[i]]*inva(ans2))%mod;
                t=(t*inva(aa[i]))%mod;
                if(root[i])t--;
                temp=(temp+ans1+t)%mod;
            }
            temp=(temp*i)%mod;
            S=(S+temp)%mod;
        }
        printf("%I64d
",S);
    }
}