题目传送门

大致题意:

给定一棵$N$个节点的树,初始点权都为$0$。有$K$次操作,每次把$(u,v)$路径上的点的权值$val$都加一。求操作完之后最大的点权。

$2\leq N \leq 50,000,1\leq K \leq 100,000$

Solution

暴力模拟呗。

每次把$u→lca(u,v)→v$路径上的点权都加一。。是肯定不行的。

于是考虑树上差分。

选择采用从下向上的差分。$val[u]$表示节点$u$的差分之后的权值。每个点的真实点权等于以它为根的子树的差分权值和(也就是树上前缀和)。

于是如果要把$u→lca(u,v)→v$路径权值加一,就val[u]++,val[v]++,val[lca(u,v)]--,val[fa[lca(u,v)]]--​;

这样操作之后,不会影响到其他节点。举个例子:

在这张图中,我们给6和5之间的点权加一。

那么真实的点权是这样的(为0的没有标出来)

转换成上述差分点权,也就是

因为$LCA(u,v)$点权只加了1,但是子树权值多了2,所以减一。而$fa[LCA(u,v)]$本不该被更改,但是这样下来就多了2,所以在$LCA(u,v)$减一的情况下再减一。而不在路径上的子树(比如图中的7)是不会被影响的。

所以$LCA$顺手倍增,时间复杂度$O(n+mlogn)$,$tarjan$据说可以跑得更快,但是我相信$O(\text{能过})$的力量!

$CODE$

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int head[N],to[N],nxt[N],cnt;
void add(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
int dep[N],fa[N][25],lg[N];
void dfs(int u,int f)
{
    dep[u]=dep[f]+1;
    fa[u][0]=f;
    for(int i=1;(1<<i)<=dep[u];i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=nxt[i])
        if(to[i]!=f)dfs(to[i],u);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y)return x;
    for(int k=lg[dep[x]];k>=0;k--)
        if(fa[x][k]!=fa[y][k])
            x=fa[x][k],y=fa[y][k];
    return fa[x][0];
}
int val[N];
int ans=-1e9;
void get(int u)
{
    for(int i=head[u];i;i=nxt[i])
        if(to[i]!=fa[u][0])get(to[i]),val[u]+=val[to[i]];
    ans=max(ans,val[u]);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int k=lca(u,v);
        val[u]++,val[v]++,val[k]--,val[fa[k][0]]--;
    }
    get(1);
    printf("%d\n",ans);
    return 0;
}
最后修改:2020 年 08 月 03 日 05 : 32 PM