Proficient.
Put your skills to the test.

Problem summary

Maintain a positively weighted tree under edge-weight changes. A query gives a start x and distinct blocked vertices, none equal to x. Find the longest distance from x along a path that avoids every blocked vertex.

Constraints

1 ≤ N,Q ≤ 200,000; total k over all queries ≤ 200,000; 1 ≤ edge weights ≤ 10^9; vertices and edges use 1-based input indices.

Worked example

An independently prepared example for this explanation.

5
1 2 1
1 4 2
2 3 3
2 5 4
10
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 1 1 5
1 1 1 2
2 1 100
1 2 0
1 2 4 1 3 4 5

5
4
7
7
7
4
2
102
0

Solution analysis

1. Root the tree at vertex 1. Record its full DFS walk with repeated parents on return, length 2N−1, and let H be root distances in this sequence. Each subtree is exactly one inclusive interval [tin,tout]. Changing an edge adds its weight difference to every H in the child subtree. Build parent jump pointers and use an iterative DFS so a chain does not overflow the call stack.
2. A segment summary stores max H, min H, max over i≤j of H[i]−2H[j], and max over i≤j of −2H[i]+H[j]. Concatenation combines extrema and the crossing pair: maxH(left)−2minH(right), or −2minH(left)+maxH(right). Adding δ to all heights adds δ to max/min and subtracts δ from both pair maxima, giving a lazy segment tree.
3. For a query, the deepest blocked ancestor of x separates x from the root. The available component lies inside the subtree of its child toward x, found by binary lifting; if no blocked ancestor exists, use the whole tree. Other relevant blocked vertices delete their subtree intervals. Sort those intervals and skip their union, retaining O(k+1) allowed intervals. Intervals nested inside an already deleted subtree need no special query.
4. Merge the allowed pieces in DFS order separately before tin[x], inside [tin[x],tout[x]], and after tout[x]. Descendants give maxH−H[x]. Before x, a farthest distance is H[x]+max(H[i]−2H[j]) for i≤j≤tin[x]; after x it is H[x]+max(−2H[j]+H[k]). Take the maximum of these three values. In the sample, blocking vertex 2 while starting at 1 leaves vertices 1 and 4, giving 2. Raising edge (1,2) to 100 makes the farthest distance from 2 equal 102 via vertex 4.

Why it works

The DFS walk has minimum height on the interval between two occurrences equal to the height of their lowest common ancestor. Consequently distance(i,x)=H[i]+H[x]−2minHeight(i..x). For endpoints preceding x, maximizing this expression is precisely the stored left-pair maximum plus H[x]; the right-pair case is symmetric. A descendant of x has distance H[i]−H[x]. Removing blocked subtrees cannot remove the lowest common ancestor of two still-allowed vertices in x’s component, and it cannot introduce a smaller height; hence these formulas remain valid after concatenating allowed pieces. The deepest blocked ancestor restricts the component to the unique child subtree containing x; every other blocked vertex inside it deletes exactly its own subtree. Thus the considered occurrences represent exactly all reachable vertices. The segment summary implements the stated maxima by considering pairs wholly in each child or crossing the split, while lazy additions preserve each formula. Edge updates and every query therefore yield the exact answer.

Watch out. When a blocked vertex is an ancestor of x, keep the child subtree toward x, not the blocked ancestor’s subtree. Exclude nested blocked intervals only once. Use the full repeated-vertex Euler walk and 64-bit distances; a preorder alone lacks LCA minima.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
#include<limits>
#include<utility>
// Algorithm: Root the tree at vertex 1.
struct Summary{
    long long maximum=0;
    long long minimum=0;
    long long leftPair=0;
    long long rightPair=0;
    bool empty=true;
};
Summary combine(const Summary&a,const Summary&b){
    if(a.empty){
        return b;
    }
    if(b.empty){
        return a;
    }
    Summary result;
    result.empty=false;
    result.maximum=std::max(a.maximum,b.maximum);
    result.minimum=std::min(a.minimum,b.minimum);
    result.leftPair=std::max({a.leftPair,b.leftPair,a.maximum-2*b.minimum});
    result.rightPair=std::max({a.rightPair,b.rightPair,-2*a.minimum+b.maximum});
    return result;
}
class SegmentTree{
    int n;
    std::vector<Summary>tree;
    std::vector<long long>lazy;
    void build(int node,int left,int right,const std::vector<long long>&h){
        if(left==right){
            tree[node]={h[left],h[left],-h[left],-h[left],false};
            return;
        }
        int middle=(left+right)/2;
        build(node*2,left,middle,h);
        build(node*2+1,middle+1,right,h);
        tree[node]=combine(tree[node*2],tree[node*2+1]);
    }
    void apply(int node,long long delta){
        tree[node].maximum+=delta;
        tree[node].minimum+=delta;
        tree[node].leftPair-=delta;
        tree[node].rightPair-=delta;
        lazy[node]+=delta;
    }
    void push(int node){
        if(lazy[node]!=0){
            apply(node*2,lazy[node]);
            apply(node*2+1,lazy[node]);
            lazy[node]=0;
        }
    }
    void add(int node,int left,int right,int from,int to,long long delta){
        if(from<=left&&right<=to){
            apply(node,delta);
            return;
        }
        push(node);
        int middle=(left+right)/2;
        if(from<=middle){
            add(node*2,left,middle,from,to,delta);
        }
        if(to>middle){
            add(node*2+1,middle+1,right,from,to,delta);
        }
        tree[node]=combine(tree[node*2],tree[node*2+1]);
    }
    Summary get(int node,int left,int right,int from,int to){
        if(from<=left&&right<=to){
            return tree[node];
        }
        push(node);
        int middle=(left+right)/2;
        Summary result;
        if(from<=middle){
            result=get(node*2,left,middle,from,to);
        }
        if(to>middle){
            result=combine(result,get(node*2+1,middle+1,right,from,to));
        }
        return result;
    }
    public:
    explicit SegmentTree(const std::vector<long long>&h)
        :n(static_cast<int>(h.size())),tree(4*n),lazy(4*n,0){
        build(1,0,n-1,h);
    }
    void add(int from,int to,long long delta){
        add(1,0,n-1,from,to,delta);
    }
    Summary get(int from,int to){
        if(from>to){
            return {};
        }
        return get(1,0,n-1,from,to);
    }
};
struct Edge{
    int to;
    int id;
    long long weight;
};
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin>>n;
    std::vector<std::vector<Edge>>graph(n);
    std::vector<long long>weight(n-1);
    for(int i=0;i<n-1;++i){
        int u,v;
        std::cin>>u>>v>>weight[i];
        --u;
        --v;
        graph[u].push_back({v,i,weight[i]});
        graph[v].push_back({u,i,weight[i]});
    }
    int levels=1;
    while((1<<levels)<=n){
        ++levels;
    }
    std::vector<std::vector<int>>up(levels,std::vector<int>(n,0));
    std::vector<int>tin(n),tout(n),depth(n,0),next(n,0),child(n-1);
    std::vector<long long>height(n,0),euler;
    std::vector<int>stack(1,0);
    tin[0]=0;
    euler.push_back(0);
    while(!stack.empty()){
        int v=stack.back();
        if(next[v]==static_cast<int>(graph[v].size())){
            tout[v]=static_cast<int>(euler.size())-1;
            stack.pop_back();
            if(!stack.empty()){
                euler.push_back(height[stack.back()]);
            }
            continue;
        }
        Edge edge=graph[v][next[v]++];
        if(edge.to==up[0][v]&&v!=0){
            continue;
        }
        int u=edge.to;
        up[0][u]=v;
        for(int level=1;level<levels;++level){
            up[level][u]=up[level-1][up[level-1][u]];
        }
        depth[u]=depth[v]+1;
        height[u]=height[v]+edge.weight;
        child[edge.id]=u;
        tin[u]=static_cast<int>(euler.size());
        euler.push_back(height[u]);
        stack.push_back(u);
    }
    SegmentTree tree(euler);
    auto ancestor=[&](int a,int b){
        return tin[a]<=tin[b]&&tout[b]<=tout[a];
    };
    int q;
    std::cin>>q;
    while(q-->0){
        int type;
        std::cin>>type;
        if(type==2){
            int id;
            long long value;
            std::cin>>id>>value;
            --id;
            int v=child[id];
            tree.add(tin[v],tout[v],value-weight[id]);
            weight[id]=value;
            continue;
        }
        int x,k;
        std::cin>>x>>k;
        --x;
        std::vector<int>blocked(k);
        int closest=-1;
        for(int&v:blocked){
            std::cin>>v;
            --v;
            if(ancestor(v,x)&&(closest==-1||depth[v]>depth[closest])){
                closest=v;
            }
        }
        int component=0;
        if(closest!=-1){
            component=x;
            int climb=depth[x]-depth[closest]-1;
            for(int level=0;level<levels;++level){
                if((climb>>level)&1){
                    component=up[level][component];
                }
            }
        }
        std::vector<std::pair<int,int>>forbidden;
        for(int v:blocked){
            if(!ancestor(v,x)&&ancestor(component,v)){
                forbidden.push_back({tin[v],tout[v]});
            }
        }
        std::sort(forbidden.begin(),forbidden.end());
        Summary before,inside,after;
        auto consume=[&](int left,int right){
            if(left>right){
                return;
            }
            before=combine(before,tree.get(left,std::min(right,tin[x])));
            inside=combine(inside,tree.get(std::max(left,tin[x]),std::min(right,tout[x])));
            after=combine(after,tree.get(std::max(left,tout[x]),right));
        };
        int cursor=tin[component];
        for(auto interval:forbidden){
            if(interval.first>cursor){
                consume(cursor,interval.first-1);
            }
            cursor=std::max(cursor,interval.second+1);
        }
        consume(cursor,tout[component]);
        long long hx=tree.get(tin[x],tin[x]).maximum;
        long long result=inside.maximum-hx;
        if(!before.empty){
            result=std::max(result,before.leftPair+hx);
        }
        if(!after.empty){
            result=std::max(result,after.rightPair+hx);
        }
        std::cout<<result<<'\n';
    }
}