COGS 2084. Asm.Def的基本算法

★☆ 输入文件：asm_algo.in 输出文件：asm_algo.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

“有句美国俗语说，如果走起来像鸭子，叫起来像鸭子，那就是一只鸭子。”斯科特·华莱士看着Asm.Def面前屏幕上滚动的绿色字符，若有所思地说。

“什么意思？”

“你的数据。看上去是一棵树。”

“按照保密条令，我什么也不说这是最好的——但见你这么热情，一句话不说也不好。”Asm.Def停下手中的快速数论变换，“确实是树。”

“然后你怎么算出来目标的位置？”

“都需要按照基本算法，按照图论的那一套理论，去产生。听说过LCA吗？不是那个印度飞机，我是说最近公共祖先……”

Asm.Def通过分析无线电信号得到了一棵有n个节点，以1为根的树。除1之外，节点i的父亲是p_i。节点带有权值，节点i的权值是w_i。

我们定义某点的祖先为从根到它路径上的所有点（包括它本身），而两个节点a、b的最近公共祖先是某个点p，使得p同时是a、b的祖先，而且p离根最远。

Asm.Def想要求出

（文字：∑∑w_i*w_j*w_LCA(i,j)），

其中LCA(i,j)是i、j的最近公共祖先，他认为这个值至关重要。由于这个值可能很大，Asm.Def只需要知道它模1,000,000,007（即10^9+7）的结果。

【输入格式】

第1行两个整数：n和w_1.

第2行到第n行，第i行有两个整数p_i和w_i。

【输出格式】

一行一个整数，即答案模1,000,000,007的值。

【样例输入】

2 2

1 1

【样例输出】

【提示】

1×1×1+1×2×2+2×1×2+2×2×2=17。

对于30%的数据，n<=100，w_i<=10。

对于60%的数据，n<=1000，w_i<=1000.

对于100%的数据，1<=n<=10^5，0<=w_i<=10^9，1<=p_i<i.

【来源】

在此键入。

Tarjan法求lca我认为是可以过的

但是需要的数组开不下数组需要 100000*99999/2 这么大三个

开不下

屠龙宝刀点击就送

#include <ctype.h>

#include <cstdio>

#include <vector>

#define mod 1000000007

#define N 150000

using namespace std;

vector<int>edge[N];

vector<int>q[N];

inline void read(int &x)

{

    register char ch=getchar();

    for(x=;!isdigit(ch);ch=getchar());

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

}

int y,Answer,u[N<<],v[N<<],ans[N<<],num,n,dep[N],fa[N],dad[N],w[N];

int find_(int x) {return x==fa[x]?x:fa[x]=find_(fa[x]);}

void dfs(int x)

{

    fa[x]=x;

    for(int i=;i<edge[x].size();i++)

    if(dad[x]!=edge[x][i]) dad[edge[x][i]]=x,dfs(edge[x][i]);

    for(int i=;i<q[x].size();i++)

    if(dad[y=u[q[x][i]]^v[q[x][i]]^x]) ans[q[x][i]]=(w[find_(y)]*)%mod;

    fa[x]=dad[x];

}

int main()

{

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

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

    read(n);

    read(w[]);

    Answer=(Answer%mod+((w[]%mod)*(w[]%mod)*(w[]%mod)%mod))%mod;

    for(int p,i=;i<=n;i++)

    {

        read(p);

        read(w[i]);

        Answer=(Answer%mod+((w[i]%mod)*(w[i]%mod)*(w[i]%mod)%mod))%mod;

        edge[i].push_back(p);

        edge[p].push_back(i);

    }

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

    {

        for(int j=;j<i;j++)

        {

            u[++num]=i;

            v[num]=j;

            q[u[num]].push_back(num);

            q[v[num]].push_back(num);

        }

    }

    dfs();

    for(int i=;i<=num;i++) Answer=(Answer%mod+((ans[i]%mod)*(w[u[i]]%mod)*(w[v[i]]%mod)%mod))%mod;

    printf("%d\n",Answer);

    return ;

}

TarjanLCA

#include <ctype.h>

#include <cstdio>

#include <vector>

#define mod 1000000007

#define N 200005

using namespace std;

typedef long long LL;

vector<LL>edge[N];

inline void read(LL &x)

{

    register char ch=getchar();

    for(x=;!isdigit(ch);ch=getchar());

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

}

LL sum[N],ans,n,w[N],siz[N],dep[N],dad[N],top[N];

void dfs(LL x)

{

    sum[x]=w[x];

    for(LL i=;i<edge[x].size();++i)

    {

        LL v=edge[x][i];

        if(dad[x]!=v)

        {

            dad[v]=x;

            dfs(v);

            ans=(ans%mod+sum[x]%mod*sum[v]%mod*w[x]%mod)%mod;

            sum[x]=(sum[x]%mod+sum[v]%mod)%mod;

        }

    }

}

int main()

{

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

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

    read(n);

    read(w[]);

    for(LL p,i=;i<=n;++i)

    {

        read(p);

        read(w[i]);

        edge[p].push_back(i);

        edge[i].push_back(p);

    }

    dfs();

    ans=ans%mod*%mod;

    for(int i=;i<=n;++i) ans=(ans%mod+w[i]%mod*w[i]%mod*w[i]%mod)%mod;

    printf("%lld\n",ans%mod);

    return ;

}

巴特西