SPOJ - QTREE

绝地灬酷狼 2022-04-15 00:29 142阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：给你一颗树，现在有两个操作，一种是改变某条边的权值，一种是查询点u到v之间的路径的最大边权。   分析：树链剖分模板题，将点权转化为边权。（树链剖分的模板题了。唯一不同的是这次权值是在边上，这样我们把每一条边的边权转移记录到深度较大的点上，因为每个点向上只有一条边，向下可能有多条边。这样我们就还是对点操作了。注意最后tp1 == tp2时，可能x != y,这样我们还需要查询x和y之间的边，因为我们的记录方式是把边   值转移到深度较大的点上，所以y下面的那条边记录在son\[y\]上。为什么是son\[y\]而不是别的儿子呢？如果x和y在lca的两边，那么tp1 == tp2时，x一定等于y。如果x或y是lca就有可能会发生tp1 == tp2时x != y的情况，tp1 == tp2说明最后x,y的top值相同，说明它们在一条重链。）参考[https://blog.csdn.net/hmc0411/article/details/78245705][https_blog.csdn.net_hmc0411_article_details_78245705]。 ##

## 代码： ##

///#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e4+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int t,n,dep[N],sz[N],pre[N],son[N],id[N],top[N],val[N],c[4*N],tot;
    
    struct edge{
        int from,to,val;
    }a[N];
    vector<vector<int> >g(N);
    
    void dfs(int u,int fa,int deep) {
        pre[u]=fa;
        sz[u]=1;
        dep[u]=deep;
        int mxson=-1;
        for(int i=0;i<g[u].size();i++) {
            int v=g[u][i];
            if(v==fa) continue;
            dfs(v,u,deep+1);
            sz[u]+=sz[v];
            if(sz[v]>mxson) mxson=sz[v],son[u]=v;
        }
    }
    
    void dfs1(int u,int topf) {
        id[u]=++tot;
        top[u]=topf;
        if(son[u]) dfs1(son[u],topf);
        for(int i=0;i<g[u].size();i++) {
            int v=g[u][i];
            if( v==pre[u] || v==son[u] ) continue;
            dfs1(v,v);
        }
    }
    
    void bd(int o,int l,int r) {
        if(l==r) {
            c[o]=val[l];
            return ;
        }
        int m=(l+r)/2;
        bd(2*o,l,m);
        bd(2*o+1,m+1,r);
        c[o]=max(c[2*o],c[2*o+1]);
    }
    
    void upd(int o,int l,int r,int pos,int val) {
        if(l==r) {
            c[o]=val;
            return ;
        }
        int m=(l+r)/2;
        if(pos<=m) upd(2*o,l,m,pos,val);
        else upd(2*o+1,m+1,r,pos,val);
        c[o]=max(c[2*o],c[2*o+1]);
    }
    
    int qy(int o,int l,int r,int ql,int qr) {
        if(ql<=l&&qr>=r) return c[o];
        int m=(l+r)/2;
        if(qr<=m) return qy(2*o,l,m,ql,qr);
        else if(ql>m) return qy(2*o+1,m+1,r,ql,qr);
        else return max(qy(2*o,l,m,ql,qr),qy(2*o+1,m+1,r,ql,qr));
    }
    
    int getmx(int x,int y) {
        int ans=-1e9;
        while(top[x]!=top[y]) {
            if(dep[top[x]]<dep[top[y]]) swap(x,y);
            ans=max(ans,qy(1,1,tot,id[top[x]],id[x]));
            x=pre[top[x]];
        }
        if(x!=y) {
            if(dep[x]>dep[y]) swap(x,y);
            ans=max(ans,qy(1,1,tot,id[son[x]],id[y]));
        }
        return ans;
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        scanf("%d",&t);
        while(t--) {
            scanf("%d",&n);
            for(int i=1;i<=n;i++) g[i].clear();
            mst(son,0);
            tot=0;
            for(int i=1;i<n;i++) {
                scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].val);
                g[a[i].from].pb(a[i].to);
                g[a[i].to].pb(a[i].from);
            }
            dfs(1,0,1);
            dfs1(1,1);
            for(int i=1;i<n;i++) {
                if(dep[a[i].from]<dep[a[i].to]) swap(a[i].from,a[i].to);
                val[id[a[i].from]]=a[i].val;
            }
            bd(1,1,tot);
            char op[10];
            int u,v;
            while(scanf("%s", op) != EOF) {
                if(op[0]=='D') break;
                else if(op[0]=='Q') {
                    scanf("%d%d",&u,&v);
                    printf("%d\n",getmx(u,v));
                }
                else if(op[0]=='C'){
                    scanf("%d%d",&u,&v);
                    upd(1,1,tot,id[a[u].from],v);
                }
            }
        }
        return 0;
    }

[Link 1]: https://vjudge.net/problem/SPOJ-QTREE
[https_blog.csdn.net_hmc0411_article_details_78245705]: https://blog.csdn.net/hmc0411/article/details/78245705