网站建设是啥工作,购物商城网站制作,模板加官网主页,建筑人才网招聘信息传送门:牛客
题目描述
奶牛们又一次试图创建一家创业公司#xff0c;还是没有从过去的经验中吸取教训–牛是可怕的管理者#xff01; 为了方便#xff0c;把奶牛从 1∼n1\sim n1∼n 编号#xff0c;把公司组织成一棵树#xff0c;1 号奶牛作为总裁#xff08;这棵树的根…传送门:牛客
题目描述
奶牛们又一次试图创建一家创业公司还是没有从过去的经验中吸取教训–牛是可怕的管理者 为了方便把奶牛从 1∼n1\sim n1∼n 编号把公司组织成一棵树1 号奶牛作为总裁这棵树的根节点。除了总裁以外的每头奶牛都有一个单独的上司它在树上的 “双亲结点”。 所有的第 iii 头牛都有一个不同的能力指数 pip_ipi描述了她对其工作的擅长程度。如果奶牛 iii 是奶牛 jjj 的祖先节点那么我们我们把奶牛 jjj 叫做 iii 的下属。 不幸地是奶牛们发现经常发生一个上司比她的一些下属能力低的情况在这种情况下上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之对于公司的中的每一头奶牛 iii请计算其下属 jjj 的数量满足 pjpip_j p_ipjpi。
输入:
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
输出:
2
0
1
0
0刚开始我以为是一道树链剖分的题目.然后发现这道题本质上应该是一道树上dfsdfsdfs的题目
当然树链剖分暴力解决这道题也是可以做的,对于树剖,复杂度时log级别的.可以考虑使用树剖将树形结构转化为线性结构,然后考虑维护区间逆序对个数.此时我们无法使用线段树进行维护.对于维护区间逆序对个数,我们考虑使用分块进行维护,朴素莫队可以在NNlogNN\sqrt{N}logNNNlogN解决.复杂度还是满足本题的.但是使用上述方法解决本题是在是杀鸡用牛刀,本题还是用不到那么复杂的维护方法的
对于本题来说,我们只需要计算一个节点的所有儿子的贡献即.因为父亲对儿子是没有贡献的,所以我们考虑使用dfsdfsdfs来解决这道题.使用权值树状数组(当然权值线段树也是可以的)来维护每一个权值.那么对于一个节点uuu来说,我们只需要遍历他的所有儿子节点,并且将所有权值都存入权值树状数组中,然后对于uuu节点的答案来说,就是当前比他大的节点的个数.但是这么做的话存在一个问题,因为我们的这棵BIT此时存的不只是当前结点的儿子的权值,之前遍历其他节点的时候也存了,所以此时会导致一些错误.解决此问题的方案是,在遍历该节点的儿子节点之前先减去之前所有已在节点的贡献即可.这样的话就相当于减去了其他不满足子树的贡献
本题需要进行离散化操作 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int tree[maxn];int n;
int lowbit(int x) {return x(~x1);
}
void Add(int pos,int val) {while(posn) {tree[pos]val;poslowbit(pos);}
}
int query(int pos) {int ans0;while(pos) {anstree[pos];pos-lowbit(pos);}return ans;
}
int w[maxn];vectorintv;int Size;
vectorintedge[maxn];int ans[maxn];
int get_id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;
}
void dfs1(int u,int per_u) {int xget_id(w[u]);ans[u]-query(Size)-query(x);for(int i0;iedge[u].size();i) {int vedge[u][i];if(vper_u) continue;dfs1(v,u);}ans[u]query(Size)-query(x);Add(x,1);
}
int main() {nread();for(int i1;in;i) {w[i]read();v.push_back(w[i]);}sort(v.begin(),v.end());Sizev.size();for(int i2;in;i) {int uread();edge[u].push_back(i);}dfs1(1,0);for(int i1;in;i) printf(%d\n,ans[i]);return 0;
}
