物流网站公司,asp网站设计,学院网站建设需求分析调研表,php大流量网站开发规范正题 题目大意
一棵树#xff0c;对于每个点#xff0c;求从任何一个在该点的子树为头#xff0c;以该点为结尾的序列必须选择这个点的最长不降子序列。 解题思路
首先我们使用权值线段树计算答案每个点(l,r,w)(l,r,w)(l,r,w)表示以l∼rl\sim rl∼r为结尾最长的不降升子序…正题 题目大意
一棵树对于每个点求从任何一个在该点的子树为头以该点为结尾的序列必须选择这个点的最长不降子序列。 解题思路
首先我们使用权值线段树计算答案每个点(l,r,w)(l,r,w)(l,r,w)表示以l∼rl\sim rl∼r为结尾最长的不降升子序列长度。
然后利用线段树维护每次跑完子节点之后将线段树合并到父节点上来计算答案。
时间复杂度O(nlogn)O(n\ log\ n)O(n log n) codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N101000;
int n,rt[N],tot,ls[N],ans[N],w[N];
struct Edge_node{int to,next;
}a[N];
struct Tree_node{int w,l,r,lson,rson;
};
vectorint q[N],c[N];
struct Line_cut_tree{Tree_node t[N*20];int tot;#define ls t[x].lson#define rs t[x].rsonint Ask(int x,int l,int r,int L,int R){if(!x) return 0; if(LlRr)return t[x].w;int mid(LR)/2;if(rmid) return Ask(ls,l,r,L,mid);else if(lmid) return Ask(rs,l,r,mid1,R);else return max(Ask(ls,l,mid,L,mid),Ask(rs,mid1,r,mid1,R));}void Change(int x,int pos,int z,int L,int R){if(!x) xtot;if(LR){t[x].wmax(z,t[x].w);return;}int mid(LR)/2;if(posmid) Change(ls,pos,z,L,mid);else if(posmid) Change(rs,pos,z,mid1,R);t[x].wmax(t[ls].w,t[rs].w);}int merge(int x,int y,int L,int R){if(!x||!y)return xy;t[x].wmax(t[x].w,t[y].w);if(LR)return x;int mid(LR)/2;t[x].lsonmerge(t[x].lson,t[y].lson,L,mid);t[x].rsonmerge(t[x].rson,t[y].rson,mid1,R);return x;}#undef ls#undef rs
}Tree;
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(int x)
{int root0;for(int ils[x];i;ia[i].next){int ya[i].to;dfs(y);rootTree.merge(root,rt[y],1,n);}ans[x]Tree.Ask(root,1,w[x],1,n)1;Tree.Change(root,w[x],ans[x],1,n);rt[x]root;
}
int main()
{scanf(%d,n);for(int i1;in;i){int x;scanf(%d,x);if(i1) continue;addl(x,i);}for(int i1;in;i)scanf(%d,w[i]);dfs(1);for(int i1;in;i)printf(%d ,ans[i]);
}
