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-15Tailwind开发入门教程:从零开始搭建第一个项目
- 2024-11-14Emotion教程:新手入门必备指南
- 2024-11-14音频生成的秘密武器:扩散模型在音乐创作中的应用
- 2024-11-14从数据科学家到AI开发者:2023年构建生成式AI网站应用的经验谈
- 2024-11-14基于AI的智能调试助手创业点子:用代码样例打造你的调试神器!
- 2024-11-14受控组件学习:从入门到初步掌握
- 2024-11-14Emotion学习入门指南
- 2024-11-14Emotion学习入门指南
- 2024-11-14获取参数学习:初学者指南
- 2024-11-14受控组件学习:从入门到实践