网站开发经常遇到的问题,网站虚拟旅游怎么做的,免费自己制作app手机软件,网站登录人数实时更新如何做题干#xff1a;
有一棵n个节点的二叉树#xff0c;1为根节点#xff0c;每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树#xff0c;都要满足#xff1a;
如果选了根节点的话#xff0c;在这棵子树内选的其他的点都要比根节点的值大#xff1b;
如…题干
有一棵n个节点的二叉树1为根节点每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树都要满足
如果选了根节点的话在这棵子树内选的其他的点都要比根节点的值大
如果在左子树选了一个点在右子树中选的其他点要比它小。
输入描述: 第一行一个整数n。
第二行n个整数wi表示每个点的权值。
接下来n行每行两个整数a,b。第i2行表示第i个节点的左右儿子节点。没有为0。
n,a,b≤105,−2×109≤wi≤2×109n,a,b≤105,−2×109≤wi≤2×109
输出描述:
一行一个整数表示答案。
示例1
输入
复制
5
1 5 4 2 3
3 2
4 5
0 0
0 0
0 0
输出
复制
3
解题报告 注意依据题意需要先遍历右子树再遍历左子树。或者存权值直接存负值然后先遍历左子树再遍历右子树(即正常dfs序)也可以。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includectime
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
int dfn[MAX],in[MAX],out[MAX];
int id,n;
int a[MAX],b[MAX];
int ans[MAX];
int w[MAX];
void dfs(int cur,int root) {dfn[id] cur;in[cur] id;if(b[cur] ! 0)dfs(b[cur],cur);if(a[cur] ! 0)dfs(a[cur],cur);out[cur] id;
}
int DP() {int len 0;for(int i 1; iid; i) dfn[i] w[dfn[i]];ans[len] dfn[1];for(int i 2; iid; i) {if(dfn[i] ans[len]) ans[len] dfn[i];else {int pos lower_bound(ans1,anslen1,dfn[i]) - ans;ans[pos] dfn[i];}}return len;
}
int main()
{cinn;for(int i 1; in; i) scanf(%d,wi);for(int i 1; in; i) scanf(%d%d,ai,bi);dfs(1,0);printf(%d\n,DP());return 0 ;
}
AC代码2
#includebits/stdc.h
using namespace std;
const int maxn 1e5 10;
int p[maxn], q[maxn], t[maxn];
int lson[maxn], rson[maxn], cnt, len;
void dfs(int rt) {if (!rt)return;dfs(lson[rt]);dfs(rson[rt]);q[cnt] p[rt]*(-1);
}
int main() {int n;cin n;for (int i 1; i n; i)cin p[i];for (int i 1; i n; i) {int x, y;cin x y;lson[i] x, rson[i] y;}dfs(1);t[1] q[1];for (int i 2; i n; i) {int cur lower_bound(t 1, t 1 len,q[i]) - t;t[cur] q[i];len max(len, cur);}cout len endl;
}
还有一种解法Orz大佬
这个dfs序(因为是后序遍历)完了之后是对离散化后的权值求最长下降子序列也就是值是1~n求最长下降子序列
#includebits/stdc.h
using namespace std;
const int N100010;
int W[N],A[N],h,B[N],lson[N],rson[N];
void dfs(int x){if (x0){return;}dfs(lson[x]);dfs(rson[x]);A[h]W[x];
}
struct Binary_Indexed_Tree{int n,bit[N];void Add(int i,int x){while (i0){bit[i]max(bit[i],x);i-i-i;}}int Query(int i){int res0;while (in){resmax(res,bit[i]);ii-i;}return res;}
}BIT;
int main(){int n,i;scanf(%d,n);for (i1;in;i){scanf(%d,W[i]);B[i]W[i];}sort(B1,B1n);int tunique(B1,B1n)-B-1;for (i1;in;i){W[i]lower_bound(B1,B1t,W[i])-B;}for (i1;in;i){scanf(%d%d,lson[i],rson[i]);}dfs(1);BIT.nt;int Ans1;for (i1;in;i){int pBIT.Query(A[i]1);BIT.Add(A[i],p1);Ansmax(Ans,p1);}printf(%d\n,Ans);return 0;
}
