HDU 4718 The LCIS on the Tree

For a sequence S  ₁, S  ₂, ... , S  _N, and a pair of integers (i, j), if 1 <= i <= j <= N and S  _i < S  _i+1 < S  _i+2 < ... < S  _j-1 < S  _j , then the sequence S  _i, S  _i+1, ... , S  _jis a  CIS (Continuous Increasing Subsequence). The longest  CIS of a sequence is called the  LCIS (Longest Continuous Increasing Subsequence).  Now we consider a tree rooted at node 1. Nodes have values. We have Q queries, each with two nodes u and v. You have to find the shortest path from u to v. And write down each nodes' value on the path, from u to v, inclusive. Then you will get a sequence, and please show us the length of its  LCIS.  Input The first line has a number T (T <= 10) , indicating the number of test cases.  For each test case, the first line is a number N (N <= 10  ⁵), the number of nodes in the tree.  The second line comes with N numbers v1, v2, v3 ... , v  _N, describing the value of node 1 to node N. (1 <= v  _i <= 10  ⁹)  The third line comes with N - 1 numbers p  ₂, p  ₃, p  ₄ ... , p  _N, describing the father nodes of node 2 to node N. Node 1 is the root and will have no father.  Then comes a number Q, it is the number of queries. (Q <= 10  ⁵)  For next Q lines, each with two numbers u and v. As described above. Output For test case X, output "Case #X:" at the first line.  Then output Q lines, each with an answer to the query.  There should be a blank line  *BETWEEN* each test case. Sample Input 1 5 1 2 3 4 5 1 1 3 3 3 1 5 4 5 2 5 Sample Output Case #1: 3 2

3

最长连续上升子串的树上版本，考虑到线性的可以使用线段树，树上的话，使用树链剖分拆成线性的即可。这题的数据貌似比较水，看到暴力的程序竟然能跑过去。

#include<map> #include<set> #include<ctime> #include<cmath> #include<stack> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define ms(x,y) memset(x,y,sizeof(x)) #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=j;i>=k;i--) #define loop(i,j,k) for (int i=j;i!=-1;i=k[i]) #define inone(x) scanf("%d",&x) #define intwo(x,y) scanf("%d%d",&x,&y) #define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z) #define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p) #define lson x<<1,l,mid #define rson x<<1|1,mid+1,r #define mp(i,j) make_pair(i,j) #define ff first #define ss second typedef long long LL; typedef pair<int, int> pii; const int low(int x) { return x&-x; } const int INF = 0x7FFFFFFF; const int mod = 1e9 + 7; const int N = 1e5 + 10; const double eps = 1e-8; int T, cas = 1, n, m, x, y; int v[N], fa[N], ft[N], nt[N], u[N], sz; int mx[N], ct[N], top[N], dep[N]; int g[N], f[N], tot; struct point { int l, r, ll, rr, mx, len; point(int l = 0, int ll = 0, int r = 0, int rr = 0, int mx = 0, int len = 0) { this->l = l; this->ll = ll; this->r = r; this->rr = rr; this->mx = mx; this->len = len; } }p[N << 2]; point merge(point a, point b) { point c; c.l = a.l; c.r = b.r; c.len = a.len + b.len; c.ll = a.ll == a.len && a.r < b.l ? a.len + b.ll : a.ll; c.rr = b.rr == b.len && b.l > a.r ? b.len + a.rr : b.rr; c.mx = max(max(a.mx, b.mx), a.r < b.l ? a.rr + b.ll : 0); return c; } void dfs(int x, int d) { mx[x] = 0; dep[x] = d; loop(i, ft[x], nt) { dfs(u[i], d + 1); mx[x] = ct[u[i]] > ct[mx[x]] ? u[i] : mx[x]; } } void Dfs(int x, int tp) { g[++tot] = x; f[x] = tot; top[x] = tp ? top[fa[x]] : x; if (mx[x]) Dfs(x, 1); loop(i, ft[x], nt) { if (u[i] == mx[x]) continue; Dfs(u[i], 0); } } void build(int x, int l, int r) { if (l == r) { p[x] = point(v[g[r]], 1, v[g[r]], 1, 1, 1); return; } int mid = l + r >> 1; build(lson); build(rson); p[x] = merge(p[x << 1], p[x << 1 | 1]); } point get(int x, int l, int r, int ll, int rr) { if (ll <= l&&r <= rr) return p[x]; int mid = l + r >> 1; if (rr <= mid) return get(lson, ll, rr); if (ll > mid) return get(rson, ll, rr); return merge(get(lson, ll, rr), get(rson, ll, rr)); } int main() { for (inone(T); T--; cas++) { inone(n); ct[0] = sz = 0; rep(i, 1, n) inone(v[i]); rep(i, 1, n) ft[i] = -1; rep(i, 2, n) { inone(fa[i]); u[sz] = i; nt[sz] = ft[fa[i]]; ft[fa[i]] = sz++; } dfs(1, 1); Dfs(1, tot = 0); printf("Case #%d:\n", cas); build(1, 1, n); for (inone(m); m--;) { intwo(x, y); point l = point(0, 0, 0, 0, 0, 0), r = point(INF, 0, INF, 0, 0, 0); while (top[x] != top[y]) { if (dep[x] > dep[y]) { l = merge(l, get(1, 1, n, f[top[x]], f[x])); x = fa[top[x]]; } else { r = merge(get(1, 1, n, f[top[y]], f[y]), r); y = fa[top[y]]; } } if (dep[x] > dep[y]) swap(x, y); l = merge(l, merge(get(1, 1, n, f[x], f[y]), r)); printf("%d\n", l.mx); } if (T) putchar(10); } return 0; }