noi.ac #525 神树的权值

「爱情、让人受尽委屈。」 2021-10-15 20:18 166阅读 0赞

mcfx神仙的题qwq

### 题目链接：[戳我][Link 1] ###

首先，我们知道30%的分还是挺好做的  
直接枚举根，然后dfs一遍以\\(O(n)\\)的时间复杂度求出来有多少神仙点  
代码如下：

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define MAXN 100010 using namespace std; int n,t; int a[MAXN],head[MAXN]; struct Edge{int nxt,to;}edge[MAXN<<1]; inline void add(int from,int to) { edge[++t].nxt=head[from],edge[t].to=to; head[from]=t; } namespace subtask1 { int ans; int kkk[MAXN]; inline void search(int x,int pre,int maxx) { for(int i=head[x];i;i=edge[i].nxt) { int v=edge[i].to; if(v==pre) continue; if(a[v]>maxx) kkk[v]=1; search(v,x,max(maxx,a[v])); } } inline void solve() { for(int p=1;p<=n;p++) { ans=0; for(int i=1;i<=n;i++) kkk[i]=0; kkk[p]=1; search(p,0,a[p]); for(int i=1;i<=n;i++) if(kkk[i]) ans+=i; printf("%d ",ans); } } } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); } if(n<=4000) subtask1::solve(); return 0; }

现在我们考虑正解。  
对于一个点x来说，它会对哪些点产生作为神仙点的贡献？  
如果x和一个点y之间可以仅通过权值小于等于\\(a\[x\]\\)的点联通，那么x一定会对点y产生贡献。  
如果我们从小到大添加点，那么当添加到x的时候，x会对所有和它联通的点产生贡献。  
我们用并查集的方式维护添加建树的过程。  
那么每个点到根的路径上的权值和就是它的答案。

对于点权相同的点，我们不能遍历到一个就合并上去，要先记录上贡献，然后再依次合并qwq

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define MAXN 300010 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();} return x*f; } int n,t; int a[MAXN],h[MAXN],fa[MAXN],head[MAXN]; long long ans[MAXN],val[MAXN]; vector<pair<int,int> >G[MAXN]; struct Edge{int nxt,to;}edge[MAXN<<1]; inline void add(int from,int to) { edge[++t].nxt=head[from],edge[t].to=to; head[from]=t; } inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} inline void dfs(int x,int pre) { ans[x]=ans[pre]+val[x]; for(int i=head[x];i;i=edge[i].nxt) { int v=edge[i].to; dfs(v,x); } } inline void solve() { for(int i=1;i<n;i++) { int x=read(),y=read(); if(a[x]<a[y]) swap(x,y); G[a[x]].push_back(make_pair(x,y)); } for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=n;i++) { for(int j=0;j<G[i].size();j++) { int x=G[i][j].first; int y=G[i][j].second; if(a[x]==a[y]) continue; if(a[x]<a[y]) swap(x,y); val[find(y)]+=x; } for(int j=0;j<G[i].size();j++) { int x=G[i][j].first; int y=G[i][j].second; if(a[x]<a[y]) swap(x,y); int xx=find(x),yy=find(y); add(xx,yy); fa[yy]=xx; } } int root=find(1); dfs(root,0); for(int i=1;i<=n;i++) printf("%lld ",ans[i]+i); } int main() { #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif n=read(); for(int i=1;i<=n;i++) a[i]=read(); solve(); return 0; }

转载于:https://www.cnblogs.com/fengxunling/p/11127071.html

[Link 1]: http://noi.ac/problem/525