noi.ac #525 神树的权值
mcfx神仙的题qwq
题目链接：戳我
首先，我们知道30%的分还是挺好做的
直接枚举根，然后dfs一遍以\(O(n)\)的时间复杂度求出来有多少神仙点
代码如下：
#include
#include
#include
#include
#include
#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 现在我们考虑正解。
对于一个点x来说，它会对哪些点产生作为神仙点的贡献？
如果x和一个点y之间可以仅通过权值小于等于\(a[x]\)的点联通，那么x一定会对点y产生贡献。
如果我们从小到大添加点，那么当添加到x的时候，x会对所有和它联通的点产生贡献。
我们用并查集的方式维护添加建树的过程。
那么每个点到根的路径上的权值和就是它的答案。
对于点权相同的点，我们不能遍历到一个就合并上去，要先记录上贡献，然后再依次合并qwq
#include
#include
#include
#include
#include
#include
#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 >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