The LCIS on the Tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 528 Accepted Submission(s): 165
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
Sample Output
Case #1:
3
2
3
Source
题意：给你一棵树，每个点都有一个权值，每个询问 u v
求 u 到 v 路径上节点权值序列的最长上升子序列
思路：数链剖分，线段树维护左到右的最长上升子序列，和右到左的最长上升子序列，
合并注意点就好了。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<bitset>
#define LL long long
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 100010
#define eps 1e-6
#define mod 1000000007
using namespace std;
struct node
{
int ls,rs,lmax,rmax,max1,max2;
int len,Lmax,Rmax;
void init()
{
ls=rs=lmax=rmax=0;
max1=max2=Lmax=Rmax=0;
len=0;
}
}tree[maxn*3];
int head[maxn],to[maxn*2],next1[maxn*2] ;
int tot,val[maxn],fa[maxn],top[maxn];
int dep[maxn],son[maxn],w[maxn];
int sz,ql,qr,n;
node v;
node Unit(node &a,node &b)
{
node ans;
ans.len=a.len+b.len ;
ans.ls=a.ls ;
ans.rs=b.rs ;
ans.max1=max(a.max1,b.max1) ;
ans.max2=max(a.max2,b.max2) ;
if(a.rs < b.ls )
{
if(a.lmax==a.len)
ans.lmax = a.lmax+b.lmax ;
else ans.lmax=a.lmax;
ans.max1=max(ans.max1,a.rmax+b.lmax) ;
if(b.rmax==b.len)
ans.rmax = a.rmax+b.rmax ;
else ans.rmax=b.rmax;
}
else {
ans.lmax = a.lmax ;
ans.rmax = b.rmax ;
}
if(b.ls < a.rs )
{
if(a.Lmax==a.len)
ans.Lmax = a.Lmax+b.Lmax ;
else ans.Lmax=a.Lmax;
ans.max2=max(ans.max2,a.Rmax+b.Lmax) ;
if(b.Rmax == b.len)
ans.Rmax = a.Rmax+b.Rmax ;
else ans.Rmax=b.Rmax;
}
else {
ans.Lmax = a.Lmax ;
ans.Rmax = b.Rmax ;
}
return ans;
}
void Unit(int u,int v)
{
to[tot]=v;next1[tot]=head[u];
head[u]=tot++;
}
void dfs(int u,int f)
{
son[u]=0;w[u]=1;
int i,v;
for( i = head[u] ; i != -1; i = next1[i])
{
v = to[i] ;
if(v==f) continue ;
fa[v]=u;
dep[v]=dep[u]+1;
dfs(v,u) ;
if(w[v]>w[son[u]])
son[u]=v;
w[u] += w[v] ;
}
}
void build(int u,int f,int t)
{
w[u]=++sz ;
top[u]=t;
if(son[u])build(son[u],u,t) ;
for( int i = head[u] ; i != -1 ; i = next1[i])
if(son[u] != to[i]&&f != to[i])
build(to[i],u,to[i]) ;
}
void init(int L,int R,int o)
{
if(L==R)
{
tree[o].ls=tree[o].rs=son[L] ;
tree[o].len=tree[o].max1=tree[o].max2=1;
tree[o].lmax=tree[o].Lmax=1;
tree[o].Rmax=tree[o].rmax = 1;
return ;
}
int mid=(L+R)>>1;
init(L,mid,o<<1) ;
init(mid+1,R,o<<1|1) ;
tree[o]=Unit(tree[o<<1],tree[o<<1|1]) ;
}
void find(int L,int R,int o)
{
if(ql<=L&&qr>=R)
{
if(v.max1==0)v=tree[o] ;
else v = Unit(v,tree[o]) ;
return ;
}
int mid=(L+R)>>1 ;
if(ql<=mid) find(L,mid,o<<1) ;
if(qr>mid) find(mid+1,R,o<<1|1);
}
int solve(int u,int vv)
{
int f1,f2;
node v1,v2;
v1.init();
v2.init();
f1=top[u];
f2=top[vv];
while(f1 != f2)
{
if(dep[f1]>dep[f2])
{
ql=w[f1];
qr=w[u] ;
v.init();
find(1,sz,1) ;
if(v1.max1==0)
v1=v;
else v1=Unit(v,v1) ;
u=fa[f1];
f1=top[u];
}
else{
ql=w[f2];
qr=w[vv] ;
v.init();
find(1,sz,1) ;
if(v2.max1==0)
v2=v;
else v2=Unit(v,v2) ;
vv=fa[f2] ;
f2=top[vv] ;
}
}
int ans=0;
if(u==vv&&0){
ans=max(v1.max2,v2.max1);
if(v1.ls < v2.ls)
{
ans=max(ans,v1.Lmax+v2.lmax) ;
}
return ans;
}
else
{
if(dep[u]>dep[vv])
{
ql=w[vv];
qr=w[u];
v.init();
find(1,sz,1) ;
if(v1.max1==0)v1=v;
else v1=Unit(v,v1) ;
}
else
{
ql=w[u];
qr=w[vv];
v.init();
find(1,sz,1) ;
if(v2.max1==0)v2=v;
else v2=Unit(v,v2) ;
}
}
ans=max(v1.max2,v2.max1);
if(v1.ls < v2.ls)
{
ans=max(ans,v1.Lmax+v2.lmax) ;
}
return ans;
}
int main()
{
int i,m,k,case1=0;
int j ,T,x,y ;
// freopen("in.txt","r",stdin);
// freopen("yy.txt","w",stdout);
bool hehe=false;
cin >> T ;
while(T--)
{
if(hehe)puts("") ;
hehe=true;
scanf("%d",&n) ;
for( i =1 ; i <= n ;i++)
scanf("%d",&val[i]) ;
tot=0;
memset(head,-1,sizeof(head)) ;
for( i = 2 ; i <= n ;i++)
{
scanf("%d",&k) ;
Unit(k,i) ;
Unit(i,k) ;
}
dep[1]=0;
fa[1]=1;
sz=0;
dfs(1,-1) ;
build(1,-1,1) ;
for( i = 1 ; i <= n ;i++)
{
son[w[i]]=val[i] ;
}
init(1,sz,1) ;
scanf("%d",&m) ;
printf("Case #%d:
",++case1);
while(m--)
{
scanf("%d%d",&x,&y) ;
printf("%d
",solve(x,y)) ;
}
}
return 0 ;
}