P3128 [USACO15DEC]最大流

秒切树上查分....（最近一次集训理解的东西）

但是，我敲了半小时才切掉这道题....

我一直迷在了“边差分”和“点差分”的区别上。

所以，先说一下此题，再说一下区别。

首先，想到差分很容易。

然后，按照戴大爷的说法，x++，y++，lca（x，y）-=2；

这是模板，统计的是每条边被经过几次。理解一下，向上前缀和时，lca向上的那条边，会被计算两次，我们既不希望它被记录，也不希望它被记录两次。

所以，要消除前面的影响，就要把它在lca“断掉”，所以只要消除这条边的影响就行了，实现就是-2；

但是，这题，要求的是点的经过数，所以，貌似不太一样了。

继续考虑，怎么消除影响而且不影响lca那个点。

首先，lca要被记录一次，但是边差分时，为了消除影响，我们减了2次。所以，可以想到，-1即可。

但是，上面的点怎么办呢？怎么消除影响呢？

很简单啊，只要把lca的father给删掉，就可以啦。

也就是fa【lca】-1;

于是，只要点差分就可以了。

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+;

int n,m;

struct edge

{

    int to,next;

}e[maxn];

int head[maxn],cnt;

inline void addedge(int from,int to)

{

    e[++cnt].next=head[from];

    e[cnt].to=to;

    head[from]=cnt;

}

int dep[maxn];

int fa[maxn][];

int son[maxn];

void dfs(int u,int f)

{

    dep[u]=dep[f]+;

    fa[u][]=f;

    son[f]=u;

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==f)

        continue;

        dfs(v,u);

    }

}

int lca(int a,int b)

{

    if(dep[a]>dep[b])

    swap(a,b);//a<b

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

    {

        if(dep[b]-(<<i)>=dep[a])

        b=fa[b][i];

    }

    if(a==b)

    return a;

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

    {

        if(fa[a][i]!=fa[b][i])

        {

            a=fa[a][i];

            b=fa[b][i];

        }

    }

    return fa[a][];

}

int dis[maxn],ans;

void dfs2(int u,int f)

{

    for(int i=head[u];i;i=e[i].next)

    {

        int v=e[i].to;

        if(v==f)

        continue;

        dfs2(v,u);

        dis[u]+=dis[v];

    }

}

int main()

{

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

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

    scanf("%d%d",&n,&m);

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

    {

        int x,y;

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

        addedge(x,y);

        addedge(y,x);

    }

    dfs(,);

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

    {

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

        {

            fa[j][i]=fa[fa[j][i-]][i-];

        }

    }

    while(m--)

    {

        int x,y;

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

        int t=lca(x,y);

        dis[x]++;

        dis[y]++;

        dis[t]-=;

        dis[fa[t][]]-=;

    }

    dfs2(,);

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

    {

        ans=max(dis[i],ans);//printf("%d ",dis[i]);

    }

    printf("%d",ans);

    return ;

}

（完）

巴特西

P3128 [USACO15DEC]最大流

最新文章

热门文章