LINK：心上秋
唐多令 宋 吴文英
何处合成愁。离人心上秋。纵芭蕉，不雨也飕飕。都道晚凉天气好，有明月，怕登楼。
年事梦中休。花空烟水流。燕辞归，客尚淹留。垂柳不萦裙带住。漫长是，系行舟。
心上秋 笔下梅 笙中月。
此题 求树上任意两点之间的最长不下降子序列 权值集合为{1~5}.
(n<=30000,m<=300000)
考虑暴力 把链抽出来然后暴力dp.最长不下降子序列的dp是nlogn的 所以总复杂度为nlognm.
优化暴力 发现权值集合很小 把链抽出来之后 设f[i][j]表示到达第i个点权值为j的最长长度 多了一个五倍的常数不过复杂度O(n) 总复杂度nm.
考虑优化 如果权值集合只有1,2怎么办？
不妨考虑倍增 设f[i][j][k][w]表示从i跳到2^j的祖先经过的边的权值从k到w的最长不降子序列的长度。
发现这个东西可以合并.
对于所有数据我们可以倍增预处理出这个数组。
对于某个询问(x,y) 我们先让x调到lca累计一个数组g[k]表示小于等于k的路径的最长长度 然后再从lca跳到y即可。
跟保卫王国的倍增dp有点像 不过我没写过那道题的倍增dp 回来可以看一下 值得一提的是这道题没有修改 所以就简单了很多。
我觉得树剖不太能写的样子 矩阵不是很好维护.
我写的有点繁琐了。大体上有一个坑点：注意g数组的维护要维护某个区间的答案 初始化和转移要注意。
在最后求答案的时候也注意由lca跳向y的时候要反着做. 数组下标也得反着.所以g数组也要有一个反着的值.
通过这道题 我们发现可以扩展到序列上 如求某段序列的最长不下降子序列 也可以使用这种倍增的方法来做。
可见倍增是优化dp的一种常用手段。
const int MAXN=30010;
int n,m,len,maxx,ans;
int ql[MAXN],qr[MAXN],wl[MAXN],wr[MAXN],top1,top2;
int g[MAXN][16][6][6],f[MAXN][16],Log[MAXN],d[MAXN],w[MAXN][6];
int lin[MAXN],ver[MAXN<<1],nex[MAXN<<1],e[MAXN<<1];
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
}
inline void dfs(int x,int father)
{
d[x]=d[father]+1;
f[x][0]=father;
rep(1,Log[d[x]],i)
{
f[x][i]=f[f[x][i-1]][i-1];
rep(1,maxx,k)
rep(1,maxx,w)
{
int s1=min(k,w),s2=max(k,w);
rep(s1,s2,l)g[x][i][k][w]=max(g[x][i][k][w],g[x][i-1][k][l]+g[f[x][i-1]][i-1][l][w]);
}
}
go(x)
{
if(tn==father)continue;
rep(e[i],maxx,j)rep(1,e[i],k)g[tn][0][j][k]=g[tn][0][k][j]=1;
dfs(tn,x);
}
}
inline void LCA(int x,int y)
{
top1=top2=0;
if(d[x]>d[y])
{
fep(Log[d[x]],0,i)
{
if(d[f[x][i]]>=d[y])
{
ql[++top1]=x;
wl[top1]=i;
x=f[x][i];
}
}
}
if(d[y]>d[x])
{
fep(Log[d[y]],0,i)
{
if(d[f[y][i]]>=d[x])
{
qr[++top2]=y;
wr[top2]=i;
y=f[y][i];
}
}
}
if(x==y)return;
fep(Log[d[x]],0,i)
{
if(f[x][i]!=f[y][i])
{
ql[++top1]=x;
wl[top1]=i;
x=f[x][i];
qr[++top2]=y;
wr[top2]=i;
y=f[y][i];
}
}
ql[++top1]=x;
wl[top1]=0;
qr[++top2]=y;
wr[top2]=0;
}
inline void get_ans()
{
ans=0;
rep(1,top1,i)
{
rep(1,maxx,j)w[i][j]=0;
rep(1,maxx,j)
rep(1,j,k)w[i][j]=max(w[i][j],w[i-1][k]+g[ql[i]][wl[i]][k][j]);
}
int l=top2;
rep(top1+1,top2+top1,i)
{
rep(1,maxx,j)w[i][j]=0;
rep(1,maxx,j)
rep(1,j,k)w[i][j]=max(w[i][j],w[i-1][k]+g[qr[l]][wr[l]][j][k]);
--l;
}
rep(1,maxx,i)ans=max(ans,w[top1+top2][i]);
}
int main()
{
freopen("1.in","r",stdin);
get(n);
rep(2,n,i)
{
int x,y,z;
get(x);get(y);get(z);
maxx=max(maxx,z);
add(x,y,z);add(y,x,z);
Log[i]=Log[i>>1]+1;
}
dfs(1,0);
get(m);
rep(1,m,i)
{
int x,y;
get(x);get(y);
LCA(x,y);
get_ans();
put(ans);
}
return 0;
}