题意
给一颗边带权的树，边权为1~5，多次询问树上某条路径组成的边权序列的LIS
思路
假设已知边权序列，设\(f_{i,j}\)表示处理了前\(i\)个数，当前\(LIS\)中的最后一个数为\(j\)时的\(LIS\)长度，显然有\(f_{i,j}=max(f_{i-1,k}+1),(k\leq j)\)，由于边权为1~5，这个算法一次是\(O(n)\)的
通过上述对\(f\)的处理的思路就可以得到倍增法
设\(fa_{rt,i}\)表示从\(rt\)向上跳\(2^i\)步到的节点 设\(g_{rt,i,j,k}\)，表示从\(rt\)向上跳\(2^i\)步得到的边权序列，当前\(LIS\)中的最小数为\(j\)，最大数为\(k\)时的\(LIS\)长度
有转移方程
\(g_{rt,i,j,k}=max(g_{rt,i-1,j,p}+g_{fa_{rt,i-1},i-1,p,k})\)
利用这个数组优化上面求\(f\)的过程即可
注意：虽然从\(y\)向\(lca\)走求的是最长不上升子序列（与\(LIS\)相反），但是可以发现\(g\)数组在\(j\geq k\)就可以表示最长不上升子序列（虽然这样与定义不符，但确实可以用）
Code
#include<bits/stdc++.h>
#define N 30005
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
using namespace std;
const int temp = 16;
int n,m,dep[N];
int dp[2][temp][6],g[N][temp][6][6],f[N][temp];
int l[N],r[N],cl,cr;//倍增时向上经过的断点
bool rev;
struct Edge
{
int next,to,dis;
}edge[N<<1];int head[N],cnt=1;
void add_edge(int from,int to,int dis)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void dfs(int rt,int fa)
{
dep[rt]=dep[fa]+1;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
f[v][0]=rt;
for(int j=1;j<=5;++j)
for(int k=1;k<=5;++k)
if(Min(j,k)<=edge[i].dis&&Max(j,k)>=edge[i].dis) g[v][0][j][k]=1;
for(int j=1;j<temp;++j)
{
f[v][j]=f[f[v][j-1]][j-1];
if(!f[v][j]) break;
for(int q=1;q<=5;++q)
for(int p=1;p<=5;++p)
for(int k=Min(p,q);k<=Max(p,q);++k)
g[v][j][q][p]=Max(g[v][j][q][p],g[v][j-1][q][k]+g[f[v][j-1]][j-1][k][p]);//attention
}
dfs(v,rt);
}
}
void init(int x,int y)
{
rev=cl=cr=0;
if(dep[x]<dep[y]) {swap(x,y);rev=1;}
for(int i=temp-1;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i],l[++cl]=i;
if(x==y) return;
for(int i=temp-1;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i],l[++cl]=i,r[++cr]=i;
l[++cl]=0; r[++cr]=0;
}
int DP(int x,int y,int cl,int cr,int l[],int r[])
{
for(int i=1;i<=cl;++i)
{
for(int j=1;j<=5;++j)//之前是j
for(int k=j;k<=5;++k)//现在是k
dp[0][i][k]=Max(dp[0][i][k],dp[0][i-1][j]+g[x][l[i]][j][k]);
x=f[x][l[i]];
}
for(int i=1;i<=cr;++i)//y相反
{
for(int j=5;j>=1;--j)//之前是j
for(int k=j;k>=1;--k)//现在是k
dp[1][i][k]=Max(dp[1][i][k],dp[1][i-1][j]+g[y][r[i]][j][k]);
y=f[y][r[i]];
}
int ans=0;
for(int i=1;i<=5;++i)
for(int j=i;j<=5;++j)
ans=Max(ans,dp[0][cl][i]+dp[1][cr][j]);
return ans;
}
int main()
{
read(n);
for(int i=1;i<n;++i)
{
int x,y,z;
read(x);read(y);read(z);
add_edge(x,y,z);
add_edge(y,x,z);
}
dfs(1,0);
read(m);
while(m--)
{
memset(dp,0,sizeof(dp));
int x,y;
read(x);read(y);
init(x,y);
printf("%d\n",rev ? DP(x,y,cr,cl,r,l) : DP(x,y,cl,cr,l,r));
}
return 0;
}
转载于:https://www.cnblogs.com/Chtholly/p/11603677.html
相关资源：微信小程序源码-合集4.rar
