R - Weak Pair
离散化+权值线段树
这个题目的初步想法，首先用dfs序建一颗树，然后判断对于每一个节点进行遍历，判断他的子节点和他相乘是不是小于等于k,
这么暴力的算法很自然的超时了。
然后上网搜了一下题解，感觉想的很巧妙。
就是我们要搜 子节点和父节点的乘积小于一个定值的对数。
一般求对数，有逆序对，都是把满足的放进去，到时候直接求答案就可以了。这个题目也很类似，但是还是有很大的区别的。
这个题目就是先把所有a[i] 和 k/a[i] 都放进一个数组，离散化，这一步是因为要直接求值，就是要把这个值放进线段树的这个离散化后的位置，权值为1 .
这个满足了a[i]*a[j]<=k 的要求，然后就是他们的关系必须是子节点和父节点。
这一点可以用dfs序来实现，先把父节点放进去，然后之后的子节点都可以查找这个节点，最后这个父节点的所有子节点都查找完之后就是把这个父节点弹出。
以上做法都是上网看题解的，我觉得还是没有那么难想了，这种差不多就是树上要满足是父节点子节点的关系都是可以用dfs来满足的。
其次就是弹出操作没有那么好想，最后就是放入线段树直接查找的这种建一棵权值线段树思想。
这个知道怎么写之后就很好写了，注意细节
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + ;
typedef long long ll;
ll sum[maxn * ], a[maxn], b[maxn], ans;
vector<int>G[maxn];
int len, f[maxn];
bool vis[maxn];
ll n, k; void update(int id, int l, int r, int pos, int val) {
if (l == r) {
sum[id] += val;
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(id << , l, mid, pos, val);
else update(id << | , mid + , r, pos, val);
sum[id] = sum[id << ] + sum[id << | ];
} ll query(int id, int l, int r, int x, int y) {
if (x <= l && y >= r) return sum[id];
int mid = (l + r) >> ;
ll ans = ;
if (x <= mid) ans += query(id << , l, mid, x, y);
if (y > mid) ans += query(id << | , mid + , r, x, y);
return ans;
} void dfs(int u) {
vis[u] = ;
int t2 = lower_bound(b + , b + + len, a[u]) - b;
update(, , len, t2, );
for (int i = ; i < G[u].size(); i++) {
int v = G[u][i];
if (vis[v]) continue;
int t1 = lower_bound(b + , b + + len, k / a[v]) - b;
ans += query(, , len, , t1);
dfs(v);
}
update(, , len, t2, -);
} int main() {
int t;
scanf("%d", &t);
while (t--) {
ans = ;
scanf("%lld%lld", &n, &k);
memset(vis, , sizeof(vis));
for (int i = ; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i], G[i].clear();
for (int i = ; i <= n; i++) b[i + n] = k / a[i];
sort(b + , b + + * n);
len = unique(b + , b + + * n) - b - ;
memset(sum, , sizeof(sum));
for (int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
vis[v] = ;
}
int root = ;
for (int i = ; i <= n; i++) {
if (vis[i] == ) {
root = i;
break;
}
}
memset(vis, , sizeof(vis));
dfs(root);
printf("%lld\n", ans);
}
return ;
}
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 2e5 + ;
typedef long long ll;
ll sum[maxn*], a[maxn], b[maxn], ans;
vector<int>G[maxn];
int len, f[maxn];
bool vis[maxn];
ll n, k;
void build(int id,int l,int r)
{
sum[id] = ;
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} void update(int id,int l,int r,int pos,int val)
{
if(l==r)
{
sum[id] += val;
return;
}
int mid = (l + r) >> ;
if(pos<=mid) update(id << , l, mid, pos, val);
else update(id << | , mid + , r, pos, val);
sum[id] = sum[id << ] + sum[id << | ];
} ll query(int id,int l,int r,int x,int y)
{
if (x <= l && y >= r) return sum[id];
int mid = (l + r) >> ;
ll ans = ;
if (x <= mid) ans += query(id << , l, mid, x, y);
if (y > mid) ans += query(id << | , mid + , r, x, y);
return ans;
} void dfs(int u)
{
vis[u] = ;
int t1 = lower_bound(b + , b + + len, k / a[u]) - b;
int t2 = lower_bound(b + , b + + len, a[u]) - b;
ans += query(, , len, , t1);
update(, , len, t2, );
for(int i=;i<G[u].size();i++)
{
int v = G[u][i];
if (vis[v]) continue;
dfs(v);
}
update(, , len, t2, -);
} int main()
{
int t;
scanf("%d", &t);
while(t--)
{
ans = ;
scanf("%lld%lld", &n, &k);
memset(vis, , sizeof(vis));
for (int i = ; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i], G[i].clear();
for (int i = ; i <= n; i++) b[i + n] = k / a[i];
sort(b + , b + + * n);
len = unique(b + , b + + * n) - b - ;
build(, , len);
for(int i=;i<n;i++)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
vis[v] = ;
}
int root = ;
for (int i = ; i <= n; i++) {
if (vis[i] == ) {
root = i;
break;
}
}
memset(vis, , sizeof(vis));
dfs(root);
printf("%lld\n", ans);
}
return ;
}