2016 大连网赛---Weak Pair(dfs+树状数组)
2018-06-17 23:48:41来源:未知 阅读 ()
题目链接
http://acm.split.hdu.edu.cn/showproblem.php?pid=5877
(1) u is an ancestor of v (Note: In this problem a node u is not considered an ancestor of itself);
(2) au×av≤k.
Can you find the number of weak pairs in the tree?
The first line of input contains an integer T denoting number of test cases.
For each case, the first line contains two space-separated integers, N and k, respectively.
The second line contains N space-separated integers, denoting a1 to aN.
Each of the subsequent lines contains two space-separated integers defining an edge connecting nodes u and v , where node u is the parent of node v.
Constrains:
1≤N≤105
0≤ai≤109
0≤k≤1018
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> using namespace std; const long long maxn=200003; long long root; long long sum,k; long long in[100005]; vector<long long>g[100005]; long long a[100005]; long long b[200005]; long long c[200005]; map<long long,long long>q; long long Lowbit(long long t) { return t&(t^(t-1)); } void add(long long x,long long t) { while(x > 0) { c[x]+=t; x -= Lowbit(x); } } long long Sum(long long li) { long long s=0; while(li<200005) { s+=c[li]; li=li+Lowbit(li); } return s; } void dfs(long long t) { long long n=g[t].size(); for(long long i=0;i<n;i++) { long long v=g[t][i]; sum+=(long long)Sum(q[a[v]]); if(a[v]==0) add(maxn,1); else add(q[k/a[v]],1); dfs(v); if(a[v]==0) add(maxn,-1); else add(q[k/a[v]],-1); } } int main() { long long T,N; scanf("%lld",&T); while(T--) { q.clear(); memset(in,0,sizeof(in)); memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); scanf("%lld%lld",&N,&k); for(long long i=1;i<=N;i++) { scanf("%lld",&a[i]); b[2*i-2]=a[i]; if(a[i]!=0) b[2*i-1]=k/a[i]; g[i].clear(); } sort(b,b+2*N); long long tot=0,pre=-1; for(long long i=0;i<2*N;i++) { if(b[i]!=pre) { pre=b[i]; q[pre]=++tot; } } for(long long i=0;i<N-1;i++) { long long aa,bb; scanf("%lld%lld",&aa,&bb); g[aa].push_back(bb); in[bb]++; } for(long long i=1;i<=N;i++) if(in[i]==0) { root=i; break; } sum=0; if(a[root]==0) add(maxn,1); else add(q[k/a[root]],1); dfs(root); printf("%lld\n",sum); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 2020年3月28日UCF Local Programming Contest 2016 2020-03-31
- 洛谷P4071-[SDOI2016]排列计数 题解 2020-01-12
- [NOIP2016]天天爱跑步-题解 2019-10-08
- CSP201612-2:工资计算 2018-09-05
- CSP201604-2:俄罗斯方块 2018-09-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash