不注册公司可以做网站吗,装饰公司为什么做网站,工业设计网站导航,新闻标题做的好的网站Description 给定一棵n个节点的有根树#xff0c;编号依次为1到n#xff0c;其中1号点为根节点。每个点有一个权值v_i。你需要将这棵树转化成一个大根堆。确切地说#xff0c;你需要选择尽可能多的节点#xff0c;满足大根堆的性质#xff1a;对于任意两个点i,j#xff0…Description 给定一棵n个节点的有根树编号依次为1到n其中1号点为根节点。每个点有一个权值v_i。 你需要将这棵树转化成一个大根堆。确切地说你需要选择尽可能多的节点满足大根堆的性质对于任意两个点i,j如果i在树上是j的祖先那么v_iv_j。 请计算可选的最多的点数注意这些点不必形成这棵树的一个连通子树。 Input 第一行包含一个正整数n(1n200000)表示节点的个数。 接下来n行每行两个整数v_i,p_i(0v_i10^9,1p_ii,p_10)表示每个节点的权值与父亲。 Output 输出一行一个正整数即最多的点数。 Sample Input 6 3 0 1 1 2 1 3 1 4 1 5 1 Sample Output 5 不容易看出这是一个变种LIS。 如果只有一条链就是LIS。 如果多条链但是最终选的点是一条链也是个树版LIS。 然后感受一下这是个LIS。 LIS有一个经典二分做法。 现在我们用set来保存二分做法的那个数组。 不同子树之间用set来启发式合并。 然后把这个点权值丢进去替换掉第一个它的。 最后输出set的大小。 一棵树每个点u有权值val[u], 要求选出最多的点并且满足每个被选的点子树中没有权值大于等于该点权值。 1 #includebits/stdc.h2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R ia;ib;i) 5 #define Rep(i,a,b) for(R ia;ib;i--) 6 #define rp(i,x) for(R iH[x];i!-1;iE[i].nt) 7 #define ms(i,a) memset(a,i,sizeof(a)) 8 #define gc() getchar() 9 templateclass Tvoid read(T x){
10 x0; char c0;
11 while (!isdigit(c)) cgc();
12 while (isdigit(c)) xx*10(c^48),cgc();
13 }
14 int const maxn2000003;
15 multisetint s[maxn];
16 int a[maxn],H[maxn],cnt,n;
17 struct Edge{
18 int to,nt;
19 }E[maxn];
20 void add(int a,int b){
21 E[cnt](Edge){b,H[a]};H[a]cnt;
22 }
23 void merge(int x,int y){
24 if(s[x].size()s[y].size()) swap(s[x],s[y]);
25 multisetint :: iterator its[x].begin();
26 for( ; it!s[x].end(); it) s[y].insert(*it) ;
27 s[x].clear();
28 }
29 void dfs(int x){
30 rp(i,x){
31 int vE[i].to;
32 dfs(v); merge(v,x);
33 }
34 multisetint :: iterator its[x].lower_bound(a[x]);
35 if(it!s[x].end()) s[x].erase(it);
36 s[x].insert(a[x]);
37 }
38 int main(){
39 read(n);
40 ms(-1,H);
41 rep(i,1,n){
42 read(a[i]);
43 int k; read(k);
44 if(k) add(k,i);
45 }
46 dfs(1);
47 printf(%d\n,s[1].size());
48 return 0;
49 } View Code 转载于:https://www.cnblogs.com/ZJXXCN/p/10457201.html
