題目鏈接：點擊查看

題目大意：中文題，不難理解

題目分析：這個題目比賽的時候沒來得及看，比賽結束后看到有大佬寫了一篇長鏈剖分+線段樹的題解就被嚇到了（主要是感覺太麻煩了，懶得去補了），讀完題后總感覺似曾相識，但是去翻以前的博客并沒有翻到，可能之前碰到過，不會做然后就勸退了吧，后來隊友和我說是虛樹模板題，昨天特意去學了一波虛樹，回頭看這個題，發現確實簡單

不難看出，松鼠的打架對于深度而言是相互獨立的，也就是說深度不同的兩個位置的松鼠是不會互相干涉的，既然這樣我們就可以枚舉深度，每次把同一深度的所有節點加上根節點用虛樹拎出來然后 dp

dp 的話也不難想，dp[ u?] 代表的是到了節點 u?為止的最大松鼠數，對于所有子節點 v 來說，如果 dp[ v ] 非零的話，那么 dp[ u ] += max( 1 , dp[ v ] - ( deep[ v ] - deep[ u ] ) )? 就好了，然后根節點特判一下

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int a[N],max_deep;vector<int>p[N];bool cmp(int x,int y);struct virtual_tree {//原樹部分 struct{int to,next;}edge[N<<1];int head[N],cnt,deep[N],dp[N][20],limit;//樹上倍增int L[N],R[N],dfn;//dfs序 void addedge(int u,int v){edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u,int fa,int dep){max_deep=max(max_deep,dep);L[u]=++dfn;deep[u]=dep;dp[u][0]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(v!=fa)dfs(v,u,dep+1);}R[u]=dfn;}int LCA(int x,int y){if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0];}void init(int n){memset(head,-1,sizeof(head));cnt=dfn=0;limit=log2(n)+1;for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}}//虛樹部分 vector<int>node[N];vector<int>ver;int Stack[N];void build(){sort(ver.begin(),ver.end(),cmp);int sz=ver.size()-1;for(int i=0;i<sz;i++)ver.push_back(LCA(ver[i],ver[i+1]));sort(ver.begin(),ver.end(),cmp);ver.erase(unique(ver.begin(),ver.end()),ver.end());int top=0;Stack[++top]=ver[0];for(int i=1;i<ver.size();i++){while(top&&R[Stack[top]]<L[ver[i]])top--;if(top)node[Stack[top]].push_back(ver[i]);Stack[++top]=ver[i];}}void clear(){for(int i=0;i<ver.size();i++)node[ver[i]].clear();}void pre(int n,int rt){for(int i=1;i<=n;i++)p[deep[i]].push_back(i);for(int i=1;i<=max_deep;i++)p[i].push_back(rt);}LL dfs2(int u){if(node[u].empty())return a[u];LL ans=0;for(auto v:node[u]){LL temp=dfs2(v);if(temp)ans+=max(1LL,temp-deep[v]+deep[u]);}return ans;}LL solve(int dep,int rt){ver=p[dep];build();LL ans=dfs2(rt);clear();return ans>1?ans-1:ans;} }tree;bool cmp(int x,int y) {return tree.L[x]<tree.L[y]; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,rt;scanf("%d%d",&n,&rt);for(int i=1;i<=n;i++)scanf("%d",a+i);tree.init(n);tree.dfs(rt,0,0);tree.pre(n,rt);LL ans=a[rt]>1?a[rt]-1:a[rt];for(int i=1;i<=max_deep;i++)ans+=tree.solve(i,rt);printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - 血压游戏(虚树+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。