Fools and Roads CodeForces

题意：给出一棵n个节点的树，还有树上的k条简单路径（用路径的两个端点u和v表示），对于树上每一条边，求出其被多少条简单路径经过。

方法：

一开始想了很久..想要在倍增求lca的同时统计边经过的次数..然而发现这样子可以统计，但是统计的值拆不开...没有办法在合适时间内得到答案...并没有思路..

想了很久发现，这其实就是个简单的树上差分，只要记录一下每个节点i到根节点路径上所有边都需要加的权值sum[i]就行了。

对于每一组(u,v)，题意操作转化为sum[u]++,sum[v]++,sum[lca(u,v)]-=2。

最后用一遍dfs把sum拆开，这个"树上前缀和"是可以O(n)拆开的。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#include<cmath>

#include<map>

using namespace std;

typedef long long LL;

typedef pair<LL,LL> P;

vector<LL> v[];

vector<P> vv;

LL T,n,ne,k;

LL deep[],anc[][],log2n,sum[],ans[];

void dfs(LL x,LL fa)

{

    LL i;

    anc[x][]=fa;

    deep[x]=deep[fa]+;

    for(i=;i<=log2n;i++)

        anc[x][i]=anc[anc[x][i-]][i-];

    for(auto y:v[x])

        if(y!=fa)

            dfs(y,x);

}

LL lca(LL x,LL y)

{

    LL t,i;

    if(deep[x]<deep[y])    swap(x,y);

    for(t=deep[x]-deep[y],i=;t>;t>>=,i++)

        if(t&)    x=anc[x][i];

    if(x==y)    return x;

    for(i=log2n;i>=;i--)

        if(anc[x][i]!=anc[y][i])

        {

            x=anc[x][i];

            y=anc[y][i];

        }

    return anc[x][];

}

void dfs2(LL x,LL fa)

{

    for(auto y:v[x])

        if(y!=fa)

            dfs2(y,x);

    ans[x]+=sum[x];sum[fa]+=sum[x];

}

int main()

{

    LL i,x,y;

    scanf("%lld",&n);log2n=log2(n);

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

    {

        scanf("%lld%lld",&x,&y);

        v[x].push_back(y);

        v[y].push_back(x);

        vv.push_back(P(x,y));

    }

    dfs(,);

    scanf("%lld",&k);

    for(i=;i<=k;i++)

    {

        scanf("%lld%lld",&x,&y);

        sum[x]++;sum[y]++;sum[lca(x,y)]-=;

    }

    dfs2(,);

    for(auto k:vv)    printf("%lld ",ans[deep[k.first]>deep[k.second]?k.first:k.second]);

    return ;

}

巴特西

Fools and Roads CodeForces - 191C

最新文章

热门文章