2016大连网络赛 Weak Pair
2024-10-12 22:59:33
Weak Pair
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
You are given a rooted tree of N nodes, labeled from 1 to N. To the ith node a non-negative value ai is assigned.An ordered pair of nodes (u,v) is said to be weak if
(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.
(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?
Input
There are multiple cases in the data set.
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.
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
Output
For each test case, print a single integer on a single line denoting the number of weak pairs in the tree.
Sample Input
1
2 3
1 2
1 2
2 3
1 2
1 2
Sample Output
1
分析:dfs+树状数组+离散化;
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=2e5+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
int n,m,k,t,h[maxn],tot,q[maxn],fa[maxn],num;
ll ans,a[maxn],b[maxn],c[maxn];
struct node
{
int to,nxt;
}e[maxn];
void add(int x,int y)
{
tot++;
e[tot].to=y;
e[tot].nxt=h[x];
h[x]=tot;
}
void gao(int x,int y)
{
for(int i=x;i<=num+;i+=(i&(-i)))
q[i]+=y;
}
int get(int x)
{
int ret=;
for(int i=x;i;i-=(i&(-i)))
ret+=q[i];
return ret;
}
void dfs(int now)
{
ans+=get(num+)-get(a[now]-);
gao(b[now],);
for(int i=h[now];i;i=e[i].nxt)
{
dfs(e[i].to);
}
gao(b[now],-);
}
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
ans=;
tot=;
j=;
ll p;
memset(h,,sizeof h);
memset(fa,,sizeof fa);
memset(q,,sizeof q);
scanf("%d%lld",&n,&p);
rep(i,,n){
scanf("%lld",&a[i]);
if(a[i]==)b[i]=1e19;
else b[i]=p/a[i];
c[j++]=a[i],c[j++]=b[i];
}
sort(c,c+j);
num=unique(c,c+j)-c;
rep(i,,n)a[i]=lower_bound(c,c+num,a[i])-c+,b[i]=lower_bound(c,c+num,b[i])-c+;
rep(i,,n-)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
fa[y]=x;
}
rep(i,,n)if(!fa[i])dfs(i);
printf("%lld\n",ans);
}
//system("Pause");
return ;
}
最新文章
- 获取EMF文件内全部文字, 并按照左上到右下的顺序排序
- mysql 5.7.11 yum 安装步骤
- 把页面上的图表导出为pdf文件,分享一种请求下载文件的方法
- SaveFileDialog的用法
- 数据结构与算法分析——C语言描述
- 【模拟】【HDU1443】 Joseph
- Productivity Improvements for the Entity Framework(实体框架设计)【转】
- iOS高效开源类库
- 使用JavaScript检测浏览器
- backtracking问题
- Head First 设计模式 第3章 装饰者模式
- ELK入门级介绍--打造实时日志查询系统
- 纯CSS打造淘宝导航菜单栏
- SSH免密登录实现
- SpreadJS使用进阶指南 - 使用 NPM 管理你的项目
- poj2100(尺取法)
- Python 基于队列的进程通信
- 实现一个简单的shell
- 【oneday_onepage】——China&#39;s Internet users grow to 591 million
- AOPR密码过滤器
热门文章
- html_web存储
- 键盘虚拟键值编码表 使用keybd_Event
- MFC中spin control使用
- 理解 php 中&; 引用
- Why isn&#39;t sizeof for a struct equal to the sum of sizeof of each member?
- 超赞!聊聊WEB APP、HYBRID APP与NATIVE APP的设计差异
- CentOS 7 rsync
- Redis配置文件 翻译 V3.2版本
- Linux系统的时区和时间调整
- Creating your own header file in C