本文共 2691 字，大约阅读时间需要 8 分钟。

参考来自：

G-血压游戏

做法：首先可以发现只有同层的松鼠才会互相打架，也就是说同层的松鼠往上走 如果 相遇 则减一

想到dp：

dp[ u ] 代表的是到了节点 u 为止的最大松鼠数，对于所有子节点 v 来说，如果 dp[ v ] 非零的话，那么 dp[ u ] += max( 1 , dp[ v ] - ( deep[ v ] - deep[ u ] ) )  就好了，然后根节点特判一下

难点就在于，不能直接在原树上跑这个dp，因为u本身还有一个a[u] 如果加上就会影响下面转移过来的dp

所以现在就将同层的点拿出来建虚树，然后跑dp即可。

说实话，看评论区说 树链剖分+线段树 我也被吓一跳，这么简单的题感觉不用这么复杂吧。然后就等了几天百度博客补题了。

/*学习虚树+lca结构体化+dij*/#include
   
    using namespace std;typedef long long ll;const ll inf=0x3f3f3f3;const int N=2e5+10;int dfn[N],numdfn;int n,root,max_deep;ll a[N];/*    lca部分*/struct LCA{    int head[N],dep[N],fa[N][22],cnt;    struct edge    {        int v,w,next;    }e[N*2];    void add(int u,int v,int w)    {        e[++cnt]={v,w,head[u]};head[u]=cnt;        e[++cnt]={u,w,head[v]};head[v]=cnt;    }    void dfs(int u,int d,int f)    {        dep[u]=d;fa[u][0]=f;        dfn[u]=++numdfn;        max_deep=max(max_deep,d);        for(int i=head[u];i;i=e[i].next)        {            int v=e[i].v;            if(v==f) continue;            dfs(v,d+1,u);        }    }    void init()    {        dfs(root,0,root);        for(int k=1;k<=20;++k)        for(int i=1;i<=n;++i)        fa[i][k]=fa[fa[i][k-1]][k-1];    }    int lca(int u,int v)    {        if(dep[u]
    
     =0;--k)            if(dep[fa[u][k]]>=dep[v]) u=fa[u][k];        if(u==v) return v;        for(int k=20;k>=0;--k)            if(fa[u][k]!=fa[v][k]) u=fa[u][k],v=fa[v][k];        return fa[u][0];    }}L;/*    虚树部分*/vector
     
      has[N],G[N];int st[N],top,cnt;int numid;bool cmp(int x,int y){    return dfn[x]
      
       1&&dfn[st[top-1]]>=dfn[fa]){        int p1=st[top],p2=st[top-1];//该相邻两节点相连        //建虚树图        G[p1].emplace_back(p2);        G[p2].emplace_back(p1);        --top;    }    if(st[top]!=fa){        int p1=st[top],p2=fa;        G[p1].emplace_back(p2);        G[p2].emplace_back(p1);        st[top]=fa;    }    st[++top]=x;}void build(int id,vector
       
        & has){    sort(has.begin(),has.end());    has.erase(unique(has.begin(),has.end()),has.end());    sort(has.begin(),has.end(),cmp);    st[top=1]=root;    for(int v:has) ins(id,v);    //printf("top:%d\n",top);    while(top>1)    {        int p1=st[top],p2=st[top-1];        G[p1].emplace_back(p2);        G[p2].emplace_back(p1);        --top;    }}ll bfs(int u,int fa){    ll ans=0;    if(u!=root&&G[u].size()==1) ans=a[u];    for(int v:G[u]){        if(v==fa) continue;        ll t=bfs(v,u);        if(t) ans+=max(1ll,t-(L.dep[v]-L.dep[u]));    }    G[u].clear();    return ans;}int main(){    scanf("%d%d",&n,&root);    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);    for(int i=1;i
        
         1) t--; ans+=t; } if(a[root]>1)a[root]--; ans+=a[root]; printf("%lld\n",ans);}/*4 294 32 72 04 32 43 1*/
        
       
      
     
    
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/105805606 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！