杭电多校第九场-1010-Jump

这场比赛是我们队回到西安之后打的第1场多校比赛。这场比赛难度比较大，题目好像我也没怎么补。所以做了5题就拿到了第2名，第1名好像有6题，然后后面的队就都是4题对。这场比赛我发挥的不错，最后的两道题都是我做的。其中一道就是这一道只有一个人过的1010。

题意：有一棵树，边有边权。你现在维护一个点的序列，操作有两种： 1.将[l,r]区间中所有点都变为其父节点（根的父节点为根节点）2.查询[l,r]区间中所有点的深度最小值

考虑sqrt分块，则我们需要处理四种操作：

1.整块变为父节点
2.块中部分节点变为父节点
3.整块询问
4.部分节点询问

我们先考虑只有1、3、4操作的情形。我们考虑建立块中所有节点的虚树，有祖先节点也在块中的节点则是永远不会成为深度最小的点的。我们去掉这些点，就得到了只有叶子节点是块中节点的一颗虚树。维护这些节点，每次操作1时都将所有点暴力变为父节点，并检查此时是否有节点是其他节点的祖先节点，及时删除没有用的节点。

由于每一个节点只会变成其父节点一次，每个块总的操作次数将不超过n。如果在更新时候维护答案，就可以直接回答3类操作。我们记录整个块被操作1进行了几次，并使用某些寻找每个节点的k祖先的方法就可以回答4类操作。

考虑2类操作，可以每次暴力重构。

事实上，不需要显式地建立虚树，只需要把有可能成为答案的点按照dfs序排序存在vector里面即可。由于将所有节点变为父节点，dfs序的相对顺序改变是有限的，因此可以线性进行这样的操作。下面是将一个这样的vector全部变为其父节点的函数的线性实现：

vector<int> cns(vector<int> Fr){
        sort(all(Fr),cmp);
        vector<int> nxt;
        for(auto ct:Fr){
            if(!nxt.size()){
                nxt.PB(ct);
                continue;
            }
            if(!subtree(nxt.back(),ct))nxt.PB(ct);
        }
        return nxt;
    }

我使用的找到祖先节点的方法是倍增，因此复杂度是n sqrt(n log n)的？如果改成O(1)的方法，可能可以达到n sqrt n，但是我没试过。

题解给出的做法如下，和我的做法并不相同，复杂度好像和我差不多。

首先我们回顾一下一个事实，就是如果我们每次删除当前树上所有度数为1的点，那么经过O(T)轮之 后，树上的度数为1的点不会超过O(n/ T) 个，我们记这些点为关键点，那么可以发现，如果一个点往上 跳了O(T)轮，那么一定在某个关键点之上，而一个关键点之上的点在一条链上，那么最浅点很容易维 护。
所以算法大致上是这样的，首先每个点到关键点之前的这一段，我们暴力跳。之后我们对于每个关键点 分别最浅的点，等价于区间减，区间最小值。
前面部分需要做O(nT) 次单点修改，O(n)次区间查询，而后面部分需要做O 次修改和查询，这 里我们假设 同阶。前面部分可以用分块将复杂度平衡成为 后面部分时间复杂度 为 所以总的时间复杂度为

代码如下。

#include <bits/stdc++.h>
using namespace std;

template <typename A, typename B>string to_string(pair<A, B> p);template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p);template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p);string to_string(const string& s) {  return '"' + s + '"';}string to_string(const char* s) {  return to_string((string) s);}string to_string(bool b) {  return (b ? "true" : "false");}string to_string(vector<bool> v) {  bool first = true;  string res = "{";  for (int i = 0; i < static_cast<int>(v.size()); i++) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(v[i]);  }  res += "}";  return res;}template <size_t N>string to_string(bitset<N> v) {  string res = "";  for (size_t i = 0; i < N; i++) {    res += static_cast<char>('0' + v[i]);  }  return res;}template <typename A>string to_string(A v) {  bool first = true;  string res = "{";  for (const auto &x : v) {    if (!first) {      res += ", ";    }    first = false;    res += to_string(x);  }  res += "}";  return res;}template <typename A, typename B>string to_string(pair<A, B> p) {  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A, typename B, typename C>string to_string(tuple<A, B, C> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";}template <typename A, typename B, typename C, typename D>string to_string(tuple<A, B, C, D> p) {  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";}void debug_out() { cerr << endl; }template <typename Head, typename... Tail>void debug_out(Head H, Tail... T) {  cerr << " " << to_string(H);  debug_out(T...);}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}

int T,n,m,rt,u,v,d,opt,l,r;
int val[450020],dfn[450020],sz[450020],d1[450020],ff[450020][20];
ll d2[450020];

vector<pii> G[450020];

int tim;
void dfs(int num,int fa = -1){
    ff[num][0] = fa;if(fa == -1)ff[num][0] = num;
    for(int i=1;i<20;i++) ff[num][i] = ff[ff[num][i-1]][i-1];
    tim+=1;
    sz[num] = 1;
    dfn[num] = tim;
    for(auto ct:G[num]){
        if(ct.F == fa)continue;
        d1[ct.F] = d1[num]+1;
        d2[ct.F] = d2[num]+ct.S;
        dfs(ct.F,num);
        sz[num]+=sz[ct.F];
    }
}
inline bool subtree(int a,int b){
    return dfn[b]<dfn[a]+sz[a] && dfn[b]>=dfn[a];
}
bool cmp(int a,int b){
    return dfn[a]<dfn[b];
}
struct block{
    int l = 1e9,r = -1,up = 0,changed = 1;
    ll cache = 0;
    vector<int> A,sig;
    vector<int> cns(vector<int> Fr){
        sort(all(Fr),cmp);
        vector<int> nxt;
        for(auto ct:Fr){
            if(!nxt.size()){
                nxt.PB(ct);
                continue;
            }
            if(!subtree(nxt.back(),ct))nxt.PB(ct);
        }
        return nxt;
    }
    void construct(){
        sig = cns(A);
    }
    void solve1(int opl,int opr){
        if(opr<l || opl>r)return;
        changed = 1;
        if(opl<=l && r<=opr){
            vector<int> nxt;
            for(auto ct:sig){
                int cc = ff[ct][0];
                if(!nxt.size()){
                    nxt.PB(cc);
                    continue;
                }
                if(subtree(nxt.back(),cc))continue;
                while(nxt.size() && subtree(cc,nxt.back()))nxt.pop_back();
                nxt.PB(cc);
            }
            sig = nxt;
            up+=1;
        }else{
            if(up){
                for(int i=0;i<18;i++){
                    if((up>>i)&1){
                        for(int j=0;j<A.size();j++)A[j] = ff[A[j]][i];
                    }
                }
                up = 0;
            }
            for(int i= max(opl,l);i<=min(opr,r);i++){
                A[i-l] = ff[A[i-l]][0];
            }
            construct();
        }
    }
    ll solve2(int opl,int opr){
        ll ans = 1e18;
        if(opr<l || opl>r)return ans;
        if(opl<=l && r<=opr){
            if(!changed)return cache;
            for(auto ct:sig)ans = min(ans,d2[ct]);
            cache = ans;
            changed = 0;
        }else{
            for(int i=0;i<18;i++){
                if((up>>i)&1){
                    for(int j=0;j<A.size();j++)A[j] = ff[A[j]][i];
                }
            }
            up = 0;
            for(int i= max(opl,l);i<=min(opr,r);i++){
                ans = min(ans,d2[A[i-l]]);
            }
        }
        return ans;
    }
};

int main() {
    read(T);
    while(T--){
        tim = 1;
        read(n,m,rt);
        d2[rt] = d1[rt] = 0;
        for(int i=0;i<n-1;i++){
            read(u,v,d);
            G[u].PB(MP(v,d));
            G[v].PB(MP(u,d));
        }
        vector<block> blocks(1010);
        for(int i=1;i<=n;i++){
            read(val[i]);
            blocks[i/300].r = max(blocks[i/300].r,i);
            blocks[i/300].l = min(blocks[i/300].l,i);
            blocks[i/300].A.PB(val[i]);
        }
        dfs(rt);
        for(auto &ct:blocks)ct.construct();
        for(int i=1;i<=m;i++){
            read(opt,l,r);
            if(opt == 1){
                for(int j=l/300;j<=r/300;j++)blocks[j].solve1(l,r);
            }else{
                ll ans = 1e18;
                for(int j=l/300;j<=r/300;j++)ans = min(ans,blocks[j].solve2(l,r));
                cout<<ans<<"\n";
            }
        }
        for(int i=0;i<n+10;i++){
            G[i].clear();
        }
    }
    return 0;
}