P5558 题解

dAniel_lele · 2023-12-27 22:16:42 · 题解

值域很小，从值域突破。先考虑序列上的区间 LIS。考虑分治，用猫树处理所有的询问，两侧 dp_{i,j,k} 表示 i 位置，值域 j\sim k 区间内的 LIS。每次向左向右扩展一个可以前缀/后缀 \max 快速转移。询问只需要枚举中间点即可。总复杂度 O(nV^2\log n+m(\log n+V))，其中 V 为值域。

考虑如何扔到树上。区间上可以分治是因为这样做可以保证每个点最多只被处理 O(\log n) 次。树上同样可以使用点分治。每次找出重心，进行一遍 dp，算出所有跨过重心的询问的答案。同样是 O(nV^2\log n+m(\log n+V)) 的。

目前最优解。

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
vector<pair<int,int>> vc[30005];
bool vis[30005];
int rt,siz[30005],tot,minv;
void getsiz(int now,int fa){
    siz[now]=1;
    for(auto v:vc[now]){
        if(v.first==fa||vis[v.first]) continue;
        getsiz(v.first,now);
        siz[now]+=siz[v.first];
    }
}
void findrt(int now,int fa){
    int maxv=0;
    siz[now]=1;
    for(auto v:vc[now]){
        if(v.first==fa||vis[v.first]) continue;
        findrt(v.first,now);
        siz[now]+=siz[v.first];
        maxv=max(maxv,siz[v.first]);
    }
    maxv=max(maxv,tot-siz[now]);
    if(maxv<minv){
        minv=maxv,rt=now;
    }
}
int dp1[30005][6][6],dp2[30005][6][6],bel[30005];
void cal(int now,int fa,int tp){
    bel[now]=tp;
    for(auto v:vc[now]){
        if(v.first==fa||vis[v.first]) continue;
        for(int i=1;i<=5;i++){
            int maxv=0;
            for(int j=i;j>=1;j--){
                maxv=max(maxv,dp1[now][j][i]);
                if(j==v.second) maxv++;
                dp1[v.first][j][i]=maxv;
            }
            maxv=0;
            for(int j=i;j<=5;j++){
                maxv=max(maxv,dp2[now][i][j]);
                if(j==v.second) maxv++;
                dp2[v.first][i][j]=maxv;
            }
        }
        if(now==rt) tp=v.first;
        cal(v.first,now,tp);
    }
}
vector<pair<pair<int,int>,int>> qry[30005];
int ans[300005];
void dfs(int now,int dep){
    memset(dp1[now],0,sizeof(dp1[now]));
    memset(dp2[now],0,sizeof(dp2[now]));
    cal(now,0,0);
    for(auto v:qry[now]){
        if(bel[v.first.first]!=bel[v.first.second]){
            for(int i=1;i<=5;i++){
                ans[v.second]=max(ans[v.second],dp1[v.first.first][1][i]+dp2[v.first.second][i][5]);
            }
        }
        else{
            qry[bel[v.first.first]].push_back(v);
        }
    }
    qry[now].clear();
    qry[now].shrink_to_fit();
    vis[now]=1;
    for(auto v:vc[now]){
        if(vis[v.first]) continue;
        rt=0;
        getsiz(v.first,now);
        tot=siz[v.first],minv=1e9;
        findrt(v.first,now);
        swap(qry[rt],qry[v.first]);
        dfs(rt,dep+1);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n; cin>>n;
    for(int i=1;i<=n;i++) vis[i]=0,vc[i].clear();
    for(int i=1;i<n;i++){
        int u,v,w; cin>>u>>v>>w;
        vc[u].push_back(make_pair(v,w));
        vc[v].push_back(make_pair(u,w));
    }
    minv=1e9;
    tot=n;
    findrt(1,0);
    int q; cin>>q;
    for(int i=1;i<=q;i++){
        int s,t; cin>>s>>t;
        qry[rt].push_back(make_pair(make_pair(s,t),i));
    }
    dfs(rt,1);
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
    return 0; 
}