C++11(clang++ 3.9) 解法, 执行用时: 178ms, 内存消耗: 12480K, 提交时间: 2019-07-27 10:20:10

#include <bits/stdc++.h>
#define DEBUG
#define debug1(x) std::cout << #x " = " << (x) << std::endl
#define debug2(x, y) std::cout << #x " = " << (x) << " ," #y " = " << (y) << std::endl
#define disp(arry, fr, to) \
    { \
        std::cout << #arry " : "; \
        for(int _i = fr; _i < to; _i++) std::cout << arry[_i] << " "; \
        std::cout << std::endl; \
    }

using namespace std;

typedef long long ll;
const int MAXV=1e5+5,MAXE=MAXV<<1;
int v,mode,dp[MAXV][2]; // 从根节点开始dfs,表示这个点等于dp[i][0]+dp[i][1]*root(mod p)

ll inv(ll x)
{
    ll ans=1;
    int up=mode-2;
    while(up)
    {
        if(up&1) ans=ans*x%mode;
        x=x*x%mode;
        up>>=1;
    }
    return ans;
}

namespace G
{
    struct Edge
    {
        int to, last, a,b,c;
        void set(int _to, int _last,int _a,int _b,int _c) { to = _to, last = _last,a=_a,b=_b,c=_c; }
    } es[MAXE];

    int top, head[MAXV],uset[MAXV];

    int get_fa(int x)
    {
        if(uset[x]==x) return x;
        return uset[x]=get_fa(uset[x]);
    }

    void init()
    {
        top = 0, memset(head, -1, sizeof(head));
        for(int i=0;i<v;++i) uset[i]=i;
    }

    bool add(int fr, int to,int a,int b,int c)
    {
        int x=get_fa(fr),y=get_fa(to);
        if(x==y) return 1;
        es[top].set(to, head[fr],a,b,c);
        head[fr] = top++;
        es[top].set(fr,head[to],b,a,c);
        head[to]=top++;
        uset[x]=y;
        return 0;
    }

    void dfs(int fr,int fa)
    {
        ll tmp;
        for(int i=head[fr],to;~i;i=es[i].last)
        {
            to=es[i].to;
            if(to==fa) continue;
            tmp=inv(es[i].b);
            dp[to][0]=tmp*((es[i].c-1ll*es[i].a*dp[fr][0])%mode)%mode;
            if(dp[to][0]<0) (dp[to][0]+=mode)%=mode;
            dp[to][1]=mode-tmp*es[i].a%mode*dp[fr][1]%mode;
            dfs(to,fr);
        }
        // debug1(fr);
        // debug2(dp[fr][0],dp[fr][1]);
    }
}

int main()
{
    scanf("%d %d",&v,&mode);
    int p1,p2;
    ll k1,k2,k3;
    G::init();
    for(int i=1,fr,to,a,b,c;i<=v;++i) 
    {
        scanf("%d %d %d %d %d",&fr,&to,&a,&b,&c);
        if(G::add(fr,to,a,b,c)) p1=fr,p2=to,k1=a,k2=b,k3=c;
    }
    // debug2(p1,p2);
    dp[1][0]=0,dp[1][1]=1;
    G::dfs(1,-1);
    ll x=(k1*dp[p1][1]+k2*dp[p2][1])%mode,y=(k3-k1*dp[p1][0]-k2*dp[p2][0])%mode;
    if(y<0) (y+=mode)%=mode;
    ll ans=y*inv(x)%mode;
    for(int i=1;i<=v;++i)
        printf("%lld\n",(dp[i][0]+dp[i][1]*ans)%mode);
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 169ms, 内存消耗: 17740K, 提交时间: 2020-05-20 14:48:35

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> pll;

const int maxn = 100000 + 50;

struct Edge
{
    LL to, next, a, b, c;
} edge[maxn << 1];

LL n, mod, X;
LL tot, head[maxn];
pll val[maxn];

void AddEdge(LL u, LL v, LL a, LL b, LL c)
{
    edge[tot] = (Edge){v, head[u], a, b, c};
    head[u] = tot++;
}

LL FastPow(LL a, LL n)
{
    LL ans = 1, base = a;
    while (n)
    {
        if (n & 1)
            (ans *= base) %= mod;
        (base *= base) %= mod;
        n >>= 1;
    }
    return ans;
}

LL GetInv(LL x)
{
    return FastPow(x, mod - 2);
}

LL Cal(pll a, pll b)
{
    LL aa = (a.first - b.first + mod) % mod;
    LL bn = GetInv((b.second - a.second + mod) % mod);
    return (aa * bn) % mod;
}

void dfs(LL u, LL pre)
{
    for (LL i = head[u]; i; i = edge[i].next)
    {
        LL v = edge[i].to;
        if (v == pre)
            continue;
        LL a = edge[i].a, b = edge[i].b, c = edge[i].c;
        LL bn = GetInv(b);
        LL nx = bn * ((c - (a * val[u].first % mod) + mod) % mod) % mod;
        LL ny = bn * (mod - a * val[u].second % mod) % mod;
        pll np = make_pair(nx, ny);
        if (val[v].first < 0)
        {
            val[v] = np;
            dfs(v, u);
        }
        else
            X = Cal(val[v], np);
    }
}

LL res[maxn];

int main()
{
    scanf("%lld%lld", &n, &mod);
    tot = 1;
    LL u, v, a, b, c;
    for (LL i = 1; i <= n; ++i)
    {
        scanf("%lld%lld%lld%lld%lld", &u, &v, &a, &b, &c);
        AddEdge(u, v, a, b, c);
        AddEdge(v, u, b, a, c);
    }
    val[1] = make_pair(0, 1);
    for (LL i = 2; i <= n; ++i)
        val[i] = make_pair(-1, -1);
    dfs(1, 0);
    for (LL i = 1; i <= n; ++i)
        res[i] = (val[i].first + val[i].second * X % mod) % mod;
    for (LL i = 1; i <= n; ++i)
        printf("%lld\n", res[i]);
    return 0;
}