正题

---

题目大意

一棵树，对于每个点，求从任何一个在该点的子树为头，以该点为结尾的序列必须选择这个点的最长不降子序列。

---

解题思路

首先我们使用权值线段树计算答案每个点$(l,r,w)$表示以$l\sim r$为结尾最长的不降升子序列长度。

然后利用线段树维护，每次跑完子节点之后将线段树合并到父节点上来计算答案。

时间复杂度$O(nlogn)$

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=101000; 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; }; vector<int> 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(L==l&&R==r)return t[x].w;int mid=(L+R)/2;if(r<=mid) return Ask(ls,l,r,L,mid);else if(l>mid) return Ask(rs,l,r,mid+1,R);else return max(Ask(ls,l,mid,L,mid),Ask(rs,mid+1,r,mid+1,R));}void Change(int &x,int pos,int z,int L,int R){if(!x) x=++tot;if(L==R){t[x].w=max(z,t[x].w);return;}int mid=(L+R)/2;if(pos<=mid) Change(ls,pos,z,L,mid);else if(pos>mid) Change(rs,pos,z,mid+1,R);t[x].w=max(t[ls].w,t[rs].w);}int merge(int x,int y,int L,int R){if(!x||!y)return x+y;t[x].w=max(t[x].w,t[y].w);if(L==R)return x;int mid=(L+R)/2;t[x].lson=merge(t[x].lson,t[y].lson,L,mid);t[x].rson=merge(t[x].rson,t[y].rson,mid+1,R);return x;}#undef ls#undef rs }Tree; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs(int x) {int root=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;dfs(y);root=Tree.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 i=1;i<=n;i++){int x;scanf("%d",&x);if(i==1) continue;addl(x,i);}for(int i=1;i<=n;i++)scanf("%d",&w[i]);dfs(1);for(int i=1;i<=n;i++)printf("%d ",ans[i]); }

总结

以上是生活随笔为你收集整理的jzoj3338-[NOI2013模拟]法法塔的奖励【权值线段树,线段树合并】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。