- The LCIS on the Tree
- Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
- Total Submission(s): 1615 Accepted Submission(s): 457
题目链接
- https://vjudge.net/problem/UVA-12655
- 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.
- 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.
- 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
题意
在一棵树上, 每次求一条路径最长连续上升子序列.
题解
一开始看错题, 以为求最长上升子序列, 然后想了好久毫无思路, 一看题解发现原来我看错题了.
连续的话就不难了.
树链剖分, 然后线段树记录一下该区间最长上升子序列, 左端点开始的最长上升子序列长度, 右端点...
反正就是考虑如果知道左子树和右子树的信息, 如何合并. 显然合并就是中间可能延长, 其他的都一样.
但是在树上, x-->lca(x,y) 和 lca(x,y)--> 是不一样的, x-->lca(x,y) 需要求最长下降子序列, 然后就是一对细节需要处理, 具体看代码吧.
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define N 500050
- struct Tree{int l,r,lb,rb,lI,rI,lD,rD,Imx,Dmx;}tr[N<<2];
- struct Edge{int from,to,s;}edges[N<<1];
- int n,m,cas,w[N];
- int tot,last[N];
- int cnt,fa[N],dp[N],size[N],son[N],rk[N],kth[N],top[N];
- template<typename T>void read(T&x)
- {
- ll k=0; char c=getchar();
- x=0;
- while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();
- if (c==EOF)exit(0);
- while(isdigit(c))x=x*10+c-'0',c=getchar();
- x=k?-x:x;
- }
- void read_char(char &c)
- {while(!isalpha(c=getchar())&&c!=EOF);}
- void AddEdge(int x,int y)
- {
- edges[++tot]=Edge{x,y,last[x]};
- last[x]=tot;
- }
- void dfs1(int x,int pre)
- {
- fa[x]=pre;
- dp[x]=dp[pre]+1;
- size[x]=1;
- son[x]=0;
- for(int i=last[x];i;i=edges[i].s)
- {
- Edge &e=edges[i];
- if (e.to==pre)continue;
- dfs1(e.to,x);
- size[x]+=size[e.to];
- if(size[e.to]>size[son[x]])son[x]=e.to;
- }
- }
- void dfs2(int x,int y)
- {
- rk[x]=++cnt;
- kth[cnt]=x;
- top[x]=y;
- if (son[x]==0)return;
- dfs2(son[x],y);
- for(int i=last[x];i;i=edges[i].s)
- {
- Edge &e=edges[i];
- if (e.to==fa[x]||e.to==son[x])continue;
- dfs2(e.to,e.to);
- }
- }
- void init(Tree &a){a=Tree{0,0,0,0,0,0,0,0,0,0};}
- template<typename T>void he(T &c,T a, T b)
- {
- if (a.Imx==0){c=b;return;}
- if (b.Imx==0){c=a;return;}
- c.l=a.l; c.r=b.r;
- int lena=a.r-a.l+1,lenb=b.r-b.l+1;
- c.lb=a.lb; c.rb=b.rb;
- c.lI=lena==a.lI&&a.rb<b.lb?lena+b.lI:a.lI;
- c.lD=lena==a.lD&&a.rb>b.lb?lena+b.lD:a.lD;
- c.rI=lenb==b.rI&&a.rb<b.lb?lenb+a.rI:b.rI;
- c.rD=lenb==b.rD&&a.rb>b.lb?lenb+a.rD:b.rD;
- c.Imx=max(a.Imx,b.Imx);
- c.Imx=max(c.Imx,a.rb<b.lb?a.rI+b.lI:0);
- c.Dmx=max(a.Dmx,b.Dmx);
- c.Dmx=max(c.Dmx,a.rb>b.lb?a.rD+b.lD:0);
- }
- void bt(int x,int l,int r)
- {
- tr[x].l=l; tr[x].r=r;
- if (l==r)
- {
- tr[x]={l,r,w[kth[l]],w[kth[l]],1,1,1,1,1,1};
- return;
- }
- int mid=(l+r)>>1;
- bt(x<<1,l,mid);
- bt(x<<1|1,mid+1,r);
- he(tr[x],tr[x<<1],tr[x<<1|1]);
- }
- Tree query(int x,int l,int r)
- {
- if (l<=tr[x].l&&tr[x].r<=r)
- return tr[x];
- int mid=(tr[x].l+tr[x].r)>>1;
- Tree tp1,tp2,tp; init(tp1); init(tp2);
- if (l<=mid)tp1=query(x<<1,l,r);
- if (mid<r)tp2=query(x<<1|1,l,r);
- he(tp,tp1,tp2);
- return tp;
- }
- int get_max(int x,int y)
- {
- int fx=top[x],fy=top[y],ans=0;
- Tree tpx,tpy,tp;
- init(tpx); init(tpy);
- while(fx!=fy)
- {
- if (dp[fx]>dp[fy])
- {
- tp=query(1,rk[fx],rk[x]);
- he(tpx,tp,tpx);
- x=fa[fx]; fx=top[x];
- }
- else
- {
- tp=query(1,rk[fy],rk[y]);
- he(tpy,tp,tpy);
- y=fa[fy]; fy=top[y];
- }
- }
- if (dp[x]>dp[y])
- {
- tp=query(1,rk[y],rk[x]);
- he(tpx,tp,tpx);
- }
- else
- {
- tp=query(1,rk[x],rk[y]);
- he(tpy,tp,tpy);
- }
- ans=max(tpx.Dmx,tpy.Imx);
- ans=max(ans,tpx.lb<tpy.lb?tpx.lD+tpy.lI:0);
- return ans;
- }
- void work()
- {
- if (cas)printf("\n");
- printf("Case #%d:\n",++cas);
- read(n);
- for(int i=1;i<=n;i++)read(w[i]);
- for(int i=2;i<=n;i++)
- {
- int x;
- read(x);
- AddEdge(x,i);
- }
- dfs1(1,0);
- dfs2(1,1);
- bt(1,1,n);
- read(m);
- for(int i=1;i<=m;i++)
- {
- int x,y;
- read(x); read(y);
- printf("%d\n",get_max(x,y));
- }
- }
- void clear()
- {
- cnt=0; tot=0;
- memset(last,0,sizeof(last));
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("aa.in","r",stdin);
- #endif
- int q;
- read(q);
- while(q--)
- {
- clear();
- work();
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3041302.html