一个备案可以做几个网站,wordpress king主题,哪个网站原创文章,乡村网站建设考虑二分求序列LIS的过程。 g[i]表示长度为i的LIS最小以多少结尾。 对于每个数#xff0c;二分寻找插入的位置来更新g数组。 放到树上也是一样#xff0c;额外加上一个合并儿子的过程。 发现儿子与儿子直接是互不影响的#xff0c;可以直接合并。 用启发式合并set来维护这个…考虑二分求序列LIS的过程。 g[i]表示长度为i的LIS最小以多少结尾。 对于每个数二分寻找插入的位置来更新g数组。 放到树上也是一样额外加上一个合并儿子的过程。 发现儿子与儿子直接是互不影响的可以直接合并。 用启发式合并set来维护这个g数组复杂度O(nlogn^2)。 #includeiostream
#includecctype
#includecstdio
#includecstring
#includestring
#includeset
#includecmath
#includectime
#includecstdlib
#includealgorithm
#define N 2200000
#define L 2000000
#define eps 1e-7
#define inf 1e97
#define ll long long
using namespace std;
inline int read()
{char ch0;int x0,flag1;while(!isdigit(ch)){chgetchar();if(ch-)flag-1;}while(isdigit(ch)){x(x3)(x1)ch-0;chgetchar();}return x*flag;
}
struct edge
{int to,nxt;
}e[N*2];
int num-1,head[N];
inline void add(int x,int y)
{e[num](edge){y,head[x]};head[x]num;e[num](edge){x,head[y]};head[y]num;
}
int w[N];
multisetints[N];
multisetint::iterator it;
void merge(int x,int y)//add y to x
{if(s[x].size()s[y].size())swap(s[x],s[y]);while(!s[y].empty()){its[y].begin();s[x].insert(*it);s[y].erase(it);}
}
void dfs(int x,int fa)
{for(int ihead[x];i!-1;ie[i].nxt){int toe[i].to;if(tofa)continue;dfs(to,x);merge(x,to);}its[x].lower_bound(w[x]);if(it!s[x].end())s[x].erase(it);s[x].insert(w[x]);
}
int main()
{memset(head,-1,sizeof(head));int nread(),x;for(int i1;in;i){w[i]read();xread();if(i!1)add(i,x);}dfs(1,1);printf(%d,(int)s[1].size());return 0;
} 转载于:https://www.cnblogs.com/Creed-qwq/p/10078893.html
