The LCIS on the Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 175 Accepted Submission(s): 40
Problem Description
For a sequence S1, S2, ... , SN, and a pair of integers (i, j), if 1 <= i <= j <= N and Si < Si+1 < Si+2 < ... < Sj-1 < Sj , then the sequence Si, Si+1, ... , Sj is 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.
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 <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 ... , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N - 1 numbers p2, p3, p4 ... , pN, 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 <= 105)
For next Q lines, each with two numbers u and v. As described above.
For each test case, the first line is a number N (N <= 105), the number of nodes in the tree.
The second line comes with N numbers v1, v2, v3 ... , vN, describing the value of node 1 to node N. (1 <= vi <= 109)
The third line comes with N - 1 numbers p2, p3, p4 ... , pN, 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 <= 105)
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.
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
5
1 2 3 4 5
1 1 3 3
3
1 5
4 5
2 5
Sample Output
Case #1:
3
2
3
3
2
3
Source
Recommend
zhuyuanchen520
用动态树把这题A掉了，
感觉很爽，一写就A了。
只有用动态树，splay维护最长连续上升子序列，注意更新操作
/* ***********************************************
Author :kuangbin
Created Time :2013-9-13 21:03:22
File Name :HDU4718.cpp
************************************************ */ #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_1(I, N) for (int I=1;I<=int(N);++I)
#define FOR_1(I, A, B) for (int I=int(A);I<=int(B);++I)
#define DWN_1(I, B, A) for (int I=int(B);I>=int(A);--I)
#define REP_C(I, N) for (int N____=int(N),I=0;I<N____;++I)
#define FOR_C(I, A, B) for (int B____=int(B),I=A;I<B____;++I)
#define DWN_C(I, B, A) for (int A____=int(A),I=B-1;I>=A____;--I)
#define REP_1_C(I, N) for (int N____=int(N),I=1;I<=N____;++I)
#define FOR_1_C(I, A, B) for (int B____=int(B),I=A;I<=B____;++I)
#define DWN_1_C(I, B, A) for (int A____=int(A),I=B;I>=A____;--I)
#define DO(N) while(N--)
#define DO_C(N) int N____ = N; while(N____--)
#define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_)
#define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_)
#define SQZ(I, J, A, B) for (int I=int(A),J=int(B)-1;I<J;++I,--J)
#define SQZ_1(I, J, A, B) for (int I=int(A),J=int(B);I<=J;++I,--J) const int MAXN = ;
int ch[MAXN][], pre[MAXN], key[MAXN];
int rev[MAXN];
int size[MAXN];
int la[MAXN], ra[MAXN], ma[MAXN];//递增的长度
int ls[MAXN], rs[MAXN], ms[MAXN];//递减的长度
int lv[MAXN], rv[MAXN];
bool rt[MAXN]; void Update_Rev(int r)
{
if(!r)return;
swap(ch[r][],ch[r][]);
swap(lv[r],rv[r]);
swap(la[r],rs[r]);
swap(ls[r],ra[r]);
swap(ma[r],ms[r]);
rev[r] ^= ;
}
void push_down(int r)
{
if(rev[r])
{
Update_Rev(ch[r][]);
Update_Rev(ch[r][]);
rev[r] = ;
}
}
void push_up(int r)
{
size[r] = size[ch[r][]] + size[ch[r][]] + ;
if(ch[r][])lv[r] = lv[ch[r][]];
else lv[r] = key[r];
if(ch[r][])rv[r] = rv[ch[r][]];
else rv[r] = key[r]; if(ch[r][] == )
{
if(ch[r][] == )
{
la[r] = ;
ls[r] = ;
}
else
{
if(key[r] < lv[ch[r][]])
la[r] = +la[ch[r][]];
else la[r] = ;
if(key[r] > lv[ch[r][]])
ls[r] = + ls[ch[r][]];
else ls[r] = ;
}
}
else
{
if(la[ch[r][]] == size[ch[r][]])
{
if(rv[ch[r][]] < key[r])
{
if(ch[r][] == )
la[r] = la[ch[r][]] + ;
else
{
if(key[r] < lv[ch[r][]])
la[r] = la[ch[r][]] + + la[ch[r][]];
else la[r] = la[ch[r][]] + ;
}
}
else la[r] = la[ch[r][]];
}
else la[r] = la[ch[r][]]; if(ls[ch[r][]] == size[ch[r][]])
{
if(rv[ch[r][]] > key[r])
{
if(ch[r][] == )
ls[r] = ls[ch[r][]] + ;
else
{
if(key[r] > lv[ch[r][]])
ls[r] = ls[ch[r][]] + + ls[ch[r][]];
else ls[r] = ls[ch[r][]] + ;
}
}
else ls[r] = ls[ch[r][]];
}
else ls[r] = ls[ch[r][]]; } if(ch[r][] == )
{
if(ch[r][] == )
{
ra[r] = ;
rs[r] = ;
}
else
{
if(key[r] > rv[ch[r][]])
ra[r] = ra[ch[r][]] + ;
else ra[r] = ;
if(key[r] < rv[ch[r][]])
rs[r] = rs[ch[r][]] + ;
else rs[r] = ;
}
}
else
{
if(ra[ch[r][]] == size[ch[r][]])
{
if(key[r] < lv[ch[r][]])
{
if(ch[r][] == )
ra[r] = ra[ch[r][]] + ;
else
{
if(key[r] > rv[ch[r][]])
ra[r] = ra[ch[r][]] + + ra[ch[r][]];
else ra[r] = ra[ch[r][]] + ;
}
}
else ra[r] = ra[ch[r][]];
}
else ra[r] = ra[ch[r][]]; if(rs[ch[r][]] == size[ch[r][]])
{
if(key[r] > lv[ch[r][]])
{
if(ch[r][] == )
rs[r] = rs[ch[r][]] + ;
else
{
if(key[r] < rv[ch[r][]])
rs[r] = rs[ch[r][]] + + rs[ch[r][]];
else rs[r] = rs[ch[r][]] + ;
}
}
else rs[r] = rs[ch[r][]];
}
else rs[r] = rs[ch[r][]]; } ma[r] = max(ma[ch[r][]],ma[ch[r][]]);
ms[r] = max(ms[ch[r][]],ms[ch[r][]]);
int tmp = ;
if(ch[r][] && key[r] > rv[ch[r][]])
tmp += ra[ch[r][]];
if(ch[r][] && key[r] < lv[ch[r][]])
tmp += la[ch[r][]];
ma[r] = max(ma[r],tmp);
tmp= ;
if(ch[r][] && key[r] < rv[ch[r][]])
tmp += rs[ch[r][]];
if(ch[r][] && key[r] > lv[ch[r][]])
tmp += ls[ch[r][]];
ms[r] = max(ms[r],tmp); }
void Rotate(int x)
{
int y = pre[x], kind = ch[y][]==x;
ch[y][kind] = ch[x][!kind];
pre[ch[y][kind]] = y;
pre[x] = pre[y];
pre[y] = x;
ch[x][!kind] = y;
if(rt[y])
rt[y] = false, rt[x] = true;
else
ch[pre[x]][ch[pre[x]][]==y] = x;
push_up(y);
}
void P(int r)
{
if(!rt[r])P(pre[r]);
push_down(r);
}
void Splay(int r)
{
P(r);
while( !rt[r] )
{
int f = pre[r], ff = pre[f];
if(rt[f])
Rotate(r);
else if( (ch[ff][]==f) == (ch[f][]==r) )
Rotate(f), Rotate(r);
else
Rotate(r), Rotate(r);
}
push_up(r);
}
int Access(int x)
{
int y = ;
for( ; x ; x = pre[y=x])
{
Splay(x);
rt[ch[x][]] = true, rt[ch[x][]=y] = false;
push_up(x);
}
return y;
}
int mroot(int r)
{
Access(r);
Splay(r);
Update_Rev(r);
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int n;
int Q;
int u,v;
scanf("%d",&T);
int iCase = ;
while(T--)
{
iCase++;
scanf("%d",&n);
for(int i = ;i <= n;i++)
{
pre[i] = ;
ch[i][] = ch[i][] = ;
rev[i] = ;
rt[i] = true;
la[i] = ra[i] = ma[i] = ;
ls[i] = rs[i] = ms[i] = ;
size[i] = ;
}
pre[] = ;
ch[][] = ch[][] = ;
rev[] = ;
rt[] = true;
la[] = ra[] = ma[] = ;
ls[] = rs[] = ms[] = ;
size[] = ; for(int i = ;i <= n;i++)
{
scanf("%d",&key[i]);
lv[i] = rv[i] = key[i];
}
for(int i = ;i <= n;i++)
scanf("%d",&pre[i]); printf("Case #%d:\n",iCase);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&u,&v);
mroot(u);
Access(v);
Splay(v);
printf("%d\n",ma[v]);
}
if(T > )printf("\n"); }
return ;
}