Weak Pair HDU - 5877 T14 D57
2021/10/7 6:12:57
本文主要是介绍Weak Pair HDU - 5877 T14 D57,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Weak Pair HDU - 5877 T14 D57
思路:
dfs过程中遇见节点就将节点保存起来,此节点递归完成后将此节点删除,树状数组保存。
注意1不一定是根节点。
参考代码
#include<bits/stdc++.h> #define ll long long #define pb push_back #define si size() using namespace std; ll read(){ll 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;} inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');} const int qs=1e5+7; ll T,n,m,k,ans,a[qs],ct,b[qs],c[qs],u[qs]; vector<int> v[qs]; int lowbit(int x){return (x&(-x));}; ll get(int x){ return lower_bound(b+1,b+1+ct,x)-b;} void add(int x,int y){for(;x<=ct;x+=lowbit(x)) c[x]+=y;} ll ask(int x){ll as=0;for(;x;x-=lowbit(x)) as+=c[x];return as;} void dfs(int x,int fa){ int f=upper_bound(b+1,b+1+ct,k/a[x])-b-1; ans=ans+ask(f); add(get(a[x]),1); for(int i=0;i<v[x].si;++i){ int p=v[x][i]; if(p==fa) continue; dfs(p,x); } add(get(a[x]),-1); } int main(){ T=read(); while(T--){ n=read(),k=read(); ans=0; int x,y; for(int i=0;i<=n;++i) v[i].clear(),c[i]=u[i]=0; for(int i=1;i<=n;++i) a[i]=read(),b[i]=a[i]; sort(b+1,b+1+n); ct=unique(b+1,b+1+n)-b-1; for(int i=1;i<n;++i){ x=read(),y=read(); v[x].pb(y); u[y]++; } int id; for(int i=1;i<=n;++i) if(!u[i]) id=i; dfs(id,0); cout<<ans<<"\n"; } return 0; }
这篇关于Weak Pair HDU - 5877 T14 D57的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-20实战:30 行代码做一个网页端的 AI 聊天助手
- 2024-11-185分钟搞懂大模型的重复惩罚后处理
- 2024-11-18基于Ollama和pgai的个人知识助手项目:用Postgres和向量扩展打造智能数据库
- 2024-11-15我用同一个提示测试了4款AI工具,看看谁设计的界面更棒
- 2024-11-15深度学习面试的时候,如何回答1x1卷积的作用
- 2024-11-15检索增强生成即服务:开发者的得力新帮手
- 2024-11-15技术与传统:人工智能时代的最后一袭纱丽
- 2024-11-15未结构化数据不仅仅是给嵌入用的:利用隐藏结构提升检索性能
- 2024-11-15Emotion项目实战:新手入门教程
- 2024-11-157 个开源库助你构建增强检索生成(RAG)、代理和 AI 搜索