移动网站建设公司,seo加wordpress工程师,用dw个人网站怎么建立,网站怎么免费注册题意
给我们一颗有根有向树 以及每个点得权值a[1]~a[n] 需要我们求出在这颗树种有多少对满足以下两个条件的pair #xff08;1#xff09;u是v的祖先节点 #xff08;2#xff09;a[u]*a[v] k N1e5 a[i]1e9 k1e18
分析
由于需要在树中找符合要求的对…题意
给我们一颗有根有向树 以及每个点得权值a[1]~a[n] 需要我们求出在这颗树种有多少对满足以下两个条件的pair 1u是v的祖先节点 2a[u]*a[v] k N1e5 a[i]1e9 k1e18
分析
由于需要在树中找符合要求的对数 一般的算法恐怕比较慢 考虑条件等式 如果我们把等式化简一下 可以得到a[u] k/a[v] 也就是说 我们对于每个点 我们可以从树中向上找祖先节点所有小于等于k/a[v]值的点的个数 也就是能和当前v点组成符合条件的对数 关键是如何快速的求得我的祖先节点有多少个符合条件的个数呢 如果建树后从当前点向上递归 或是从根节点向下递归 向上递归每个节点 都需要走所有的父亲节点 最终的复杂度接近O(n^2) 从根节点向下递归 需要记录每个节点的值 不好实现 考虑如果我们把值元素插入到树状数组中 那么也就是说 每次对于当前节点我们只需要到 树状数组中查找有多少个点 满足不能是要求不就行了吗 复杂度O(n*logn) 那么如何保证查到的都是祖先节点呢 我们就需要从根节点开始dfs查找 每次对于一个新节点 我们查找符合条件的点 查完后把当前点插入进去 每次dfs回溯回来的时候就把该点的标记删除掉 以防影响其他搜索枝的查找 为何采用DFS这样就能保证每次查找一个节点 所有的祖先节点以及查找插入过了 那么关于1e9我们可以离散化为每次输入的节点数量1e5 为了使不等式大小关系不变 我们需要把每个节点的值和k/权值 也算作输入数据的一部分 因为只有这样 才能保证相对大小不变 离散化后 仍然符合原来数值的大小关系
离散化
void Discret(){sort(li1,li1(n1));//对数组中每个元素的大小排名siz unique(li1,li1(n1))-li;//去重步骤 rep(i,1,n1)a[i] lower_bound(li1,li1siz,a[i])-li;// 查找排序去重后 原来的元素大小的位置赋值给原来的元素才能正确离散化
}
code
#include iostream
#include cstdio
#include algorithm
#include cstring
#include queue
#include vectorusing namespace std;
typedef long long ll;
const int N 1e510;ll a[N1],li[N1],k,ans;
int tre[N1],n;
int bok[N];
vectorinte[N];void Discret(){for(int i1;in*2;i)li[i] a[i];sort(li1,li1n*2);int siz unique(li1,li1n*2)-li-1;// unique 前提是有序数组for(int i1;in*2;i)a[i] lower_bound(li1,li1siz,a[i])-li;// 只有查找排序去重后 拿原来的元素找位置才能正确离散化
}
int sum(int x){int s0;while(x0){stre[x];x-x(-x);}return s;
}
void add(int x,int val)
{while(xn*2){tre[x]val;xx(-x);}
}
void dfs(int rt)
{anssum(a[rtn]);add(a[rt],1);for(int i0;ie[rt].size();i)dfs(e[rt][i]);add(a[rt],-1);
}
int main()
{int t;scanf(%d,t);while(t--){ans0;memset(tre,0,sizeof(tre));memset(bok,0,sizeof(bok));scanf(%d%lld,n,k);for(int i1;in;i)e[i].clear();for(int (i)1;(i)n;(i)){scanf(%lld,a[i]);if(a[i]0)a[in]1e18;else a[in] k/a[i];}Discret();for(int i1;in;i){int u,v;scanf(%d%d,u,v);e[u].push_back(v);bok[v];}for(int i1;in;(i)){if(!bok[i]){dfs(i);break;}}// 就是这忘记加括号了printf(%lld\n,ans);}return 0;
}WA了好几十发 发现最后跳出循环的括号没加WTF。。。写代码时还是最好不要挤在一行写 容易眼缺。。。
