5月qbxtD6T3

zhqwq · 2020-05-09 14:58:46 · 个人记录

边权带修，查询距离某个点最远点的距离。

错误的想法：树上动态DP

正确的想法：用树链剖分维护。

链剖的套路似乎是维护一下自己轻儿子的某些信息（树上动态DP也有这个操作？）

对于这个题来说，要维护的信息是：维护每个点轻子树中，深度最大的点的深度-这个点自己的深度的二倍（注意只考虑了轻子树）

我：？？？

意思就是说，因为u到v的路径长为dep[u]+dep[v]-2*dep[lca]

查询时，dep[u]是已知的，所以只需最大化dep[v]-2*dep[lca]即可。

查询时，我们树剖之后，我们不是把u到根的路径剖成重链和轻边嘛

蓝色边为重链，粉色边为轻边。

我们现在的查询的u设为最下面的那个点。

我们考虑它的lca是什么。当lca为重链上的点时，那可能成为v的点一定是在lca的轻儿子里（因为u就在lca的重儿子里）。

直接利用我们上面对每个点维护的dep[v]-2*dep[lca]的信息即可。于是重链上的直接用线段树维护就行了（大概？）

当lca为轻边上的点（就是粉色的那个点），这时你不能直接用dep[v]-2*dep[lca]这个信息了。因为这时v的取值不是轻子树，而是Q除了u所在子树之外的其它子树。

这，，其实是并不难做的。

因为轻边只有log条，所以这种情况只会遇到log次。

假设Q子树的dfs序为[l1,r1]，R为[l2,r2]，那么v的取值范围就是[l1,l2-1]和[r2+1,r2]

再开个线段树，下标为dfs序，维护区间深度的最大值即可。

捋一下思路：我们维护了两套东西：对于重链上的点，维护dep[v]-2*dep[lca]（lca就是这个点，v是在它轻儿子子树里的点）的最大值。

每次查询直接插这条重链的最大值即可。

对于轻边上的点（呃具体来说应该是某条轻边较靠上的点）

v的可能取值是[l1,l2-1]和[r2+1,r2]

用另一个线段树维护区间深度最大值即可。

那带修时，我们也考虑怎么维护这两套东西。

假设修改了一条边，首先，第二个线段树是好维护的。

因为那个线段树只是对dfs序维护了每个点的深度。

你把一条边边权改变后，只有那条边下面的子树里所有点的深度会变化相同的值，直接做区间加即可。

对于dep[v]-2*dep[lca]这个东西，和动态DP似乎差不多，设改变了<x,y>这条边的边权，x到根的路径，重链上的点的值是不变的，变的只有轻边（靠上的）那个点。

既然只有log个点的值变化了，也可以相对暴力得维护：还是利用第二棵线段树：

和查询时处理轻儿子的情况类似，你考虑目前v的取值是这个点子树的dfs序区间[l1,r1]，挖去它的重儿子子树的那段区间[l2,r2]。那v的可能取值是[l1,l2-1]和[r2+1,r2]

查询区间深度最大值即可。

于是这个题就做完了。

另一种做法：

众所周知，距离树上某个点最远的点，一定是任意一条直径的两端点其中的一个。

老师讲了一个证明，贴在最后面8！

那如果我们能维护边带修的动态直径（的两个端点U,V），那就可以容易地解决这个问题了！

等等，先考虑这么个问题：假设我们已经求出U,V了，怎么求x到U的距离和u到V的距离？

你的边带修了啊，暴力的想法是直接树剖，但其实不需要。

开一个线段树，下标为dfs序，维护每个点的深度，那u到U的距离就是dep[u]+dep[U]-2*dep[lca(u,U)]（树的形态没变，lca可以直接维护。

边修改其实是改了一个子树内所有点的dep

（其实就是第一种做法的“第二棵线段树”嘛）

不过这里你甚至不需要求区间最大值，只需要区间加和单点查询即可。

如何动态维护直径？

（如果你会这道题的话，有个结论是一条边边权改变，直径最多只有一个端点移动，于是你分别查到直径俩端点距离最长的点即可。）

如果不会这道题，还有另一种方法：

首先，定义一下树上任意一个点集S的直径。

定义为：x,y∈S,dis(x,y)的最大值，这里的dis(x,y)是他们在原树上的距离。

也就是说，直径可以经过不在点集上的点，只要求端点必须在点集内。

然后又有个性质：假设S1的直径为<u_1,v_1>，S2的直径为<u_2,v_2>，那么 S1\cup S2的直径的端点一定是u1,v1,u2,v2中的两个（证明见下）

有了这个性质，可以直接对dfs序新建一棵线段树，维护的是区间里所有点这个点集的直径的俩端点。

于是做完了。

update：写博客的时候口胡就好了，真正写的时候发现有亿些问题：

怎么modify啊？

当我们修改一条边边权的时候怎么modify啊？

好像既不是单点修改也不是正常的区间修改啊。。然后老师也没有给代码，网上也找不到有关资料。。。

然后自己脑补了一下：

注意咱们线段树维护的是一段dfn区间上各点形成的点集的直径。

假设修改了<u,v>这条边（v深度大）

如果这个点集完全在v子树内，或者和v子树完全没交集，那它们的直径一定不会有变化（因为简单路径嘛，你总不能经过<u,v>再从<u,v>走回来。）

也就是说改变的是，和v子树有交集，却没被v子树完全包含的区间。

对应到dfn序上，就形如右图。（黑色的是v子树在dfn上范围。蓝色的不可行，粉色的可行）。

那我们的做法很暴力——修改线段树上每个这样的区间，如果不需要修改return，否则递归处理。（如下图，×的是不递归，√的是递归（叶子结点直接return了））

复杂度看上去很窒息——但我们仔细想想，这个过程似乎和我们普通线段树上区间查询很像——：

如果完全包含直接return答案，如果完全没交压根不递归（或者说return0/INF一类的事情对吧，对答案无影响即可）

这里不也一样吗，所以看起来只需要修改log个区间。（这个idea可不可以拿来出题啊hhh

但，，并过不了，TTTTT

我感jio复杂度是对的……吧

可能是因为这个代码的巨巨巨巨巨大常数。

然后我拿下来拍了拍，大概能在6-7s内出结果（可是我树剖版本在本机也差不多这么慢啊hhhhh为啥树剖过了这个过不了。。。哭）

或许可以继承一下子树直径长度，这样每次update只需要求4条路径长度而不是6条（不知有木有用。。。。）

证明树上到一个点距离最远的点之一一定是任意直径的某一个端点

老师：画个图就非常简单了！

现在要求距离X最远的点，

分类讨论一下，可以发现，可能成为距离X最远的点，本质不同的只有下图y点z点两种情况

Case 1：

假设y为距离x最远的点。

那么有dis(x,v)<dis(x,y)，则有dis(P,v)<dis(P,y)

那毁了，可以推出dis(u,y)>dis(u,v)，这与(u,v)是直径矛盾

Case 2：

假设z为距离x最远的点，与Case1类似

可以推出dis(Q,z)>dis(Q,v)

那么dis(u,z)>dis(u,v)，又与(u,v)是直径矛盾。

因而就得证了。

（似乎我当时也是这么想的）

证明两点集的并的直径，端点一定是两点集内部直径的四个端点中的两个：假设红色的点在一个点集，直径为(u1,v1)；蓝色的点在一个点集，直径为(u2,v2)，分类讨论：

Case1：

如果两个集合相交了，相交于P

如果(u1,x)是并集的直径，那么有dis(P,x)>dis(P,v2)，那可以推出dis(u2,x)>dis(u2),v矛盾。

Case2：

如果两集合不相交，但他们必定还是有边相连的

如果(u1,x)是并集的直径，那么有dis(Q,x)>dis(Q,v2)，那可以推出dis(u2,x)>dis(u2),v矛盾。

可以注意到，上面的讨论并没有用到点集联通之类的信息，于是可以证明了。

并且上面的分类讨论应该是不完全的，，但，，反正就是这种感觉啦hhh

第一种方法的代码

写一点调一点还好，要是让我整个写完再调可能需要调到下辈子hhh

(6kb，写过的人都说好

有个细节是，上面讨论的做法只考虑了u向上走的情况，向下走的（也即在u子树内部走的），随便处理一下即可。。。

#include<algorithm>
#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f3f3f3f3f
#define I inline
#define R register
#define Root 1,n,1
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
#define Ls rt<<1
#define Rs rt<<1|1 
using std::cout;
using std::endl;
using std::max;
using std::min;

int read(){
    int h=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+c-'0',c=getchar();
    return h;
}

//longlong 
const int MAXN=404000; 
int n,m;

struct Edge{
    int to;
    int nxt;
    int dis; 
}edge[MAXN];
int frm[MAXN];
int cnt_e;

void insert(int u,int v,int w){
    cnt_e++;
    edge[cnt_e].to=v;
    edge[cnt_e].nxt=frm[u];
    edge[cnt_e].dis=w;
    frm[u]=cnt_e;
}

int dep[MAXN];long long depth[MAXN];//dep为不带权深度，树剖时用；depth为带权深度，求两点距离时用 
int fa[MAXN];
int siz[MAXN];
int mson[MAXN];//维护这四个 

void dfs1(int x,int f,int w){
    dep[x]=dep[f]+1;depth[x]=depth[f]+w;
    fa[x]=f;
    siz[x]=1;
    int mxn=0;
    for(int i=frm[x];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v!=f){
            dfs1(v,x,edge[i].dis);
            siz[x]+=siz[v];
            if(siz[v]>mxn){
                mson[x]=v;
                mxn=siz[v];
            }
        }
    }
}

int dfn[MAXN];//dfs序 
int id[MAXN];//原编号 
int top[MAXN];//链头 
int cnt_d;
long long ww[MAXN];//初始状态depth[v]-2*depth[x]的最大值，其中v是x的轻儿子子树中任意点，建t2时用
//特别地，如果x没有轻子树，那就把它赋成-depth[x]。看着就很有道理对吧 
long long mxd[MAXN];//初始状态，每个点所有儿子depth的最大值。求ww时用。
//两数组下表均为原编号 

void dfs2(int x,int tp){
    dfn[x]=++cnt_d,id[cnt_d]=x;
    top[x]=tp;
    mxd[x]=depth[x],ww[x]=-depth[x];//ww赋这样的初值，是因为depth[v]-2*depth[x]一定比 -depth[x]大，如果有轻儿子一定会被更新 
    if(!mson[x])return;
    dfs2(mson[x],tp);//先递归重儿子 
    mxd[x]=max(mxd[x],mxd[mson[x]]);

    for(int i=frm[x];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v!=fa[x]&&v!=mson[x]){
            dfs2(v,v);
            mxd[x]=max(mxd[x],mxd[v]); 
            ww[x]=max(ww[x],mxd[v]-2*depth[x]);
        }
    }
}

//t1对dfs序维护深度。支持单点查询（可用区间查最值实现），区间查最值，和区间加减。
//t2下标还是dfs序（树剖嘛），对每个点x维护depth[v]-2*depth[x]的最大值，其中v是x的轻儿子子树中任意点；支持单点赋值和区间求最大值 
struct Segment_Tree1{
    long long mx[MAXN<<2];//区间最大值 
    long long col[MAXN<<2];//区间加标记 
    void build(int l,int r,int rt,long long* A){
        if(l==r){
            mx[rt]=A[id[l]];//注意depth/ww的下标是原编号
            return; 
        }
        int mid=(l+r)>>1;
        build(Lson,A);build(Rson,A);
        mx[rt]=max(mx[Ls],mx[Rs]);
    }

    I void push_down(int rt){
        col[Ls]+=col[rt],col[Rs]+=col[rt];
        mx[Ls]+=col[rt],mx[Rs]+=col[rt];//区间每个数都加嘛w
        col[rt]=0; 
    }

    long long query(int l,int r,int rt,int nowl,int nowr){//查询区间最大值 
        if(nowr<nowl)return -INF;//这种情况在代码里是可能出现的hhh 
        if(nowl<=l&&r<=nowr)return mx[rt];
        if(col[rt])push_down(rt);
        int mid=(l+r)>>1; 
        if(nowl<=mid){
            if(nowr>mid)return max(query(Lson,nowl,nowr),query(Rson,nowl,nowr));
            return query(Lson,nowl,nowr);
        }
        return query(Rson,nowl,nowr);
    }

    void modify1(int l,int r,int rt,int nowl,int nowr,int k){//区间加 
        if(nowl<=l&&r<=nowr){
            mx[rt]+=k,col[rt]+=k;
            return; 
        }
        push_down(rt);
        int mid=(l+r)>>1;
        if(nowl<=mid)modify1(Lson,nowl,nowr,k);
        if(nowr>mid)modify1(Rson,nowl,nowr,k);
        mx[rt]=max(mx[Ls],mx[Rs]);//差点忘了updatehh 
    }

    void modify2(int l,int r,int rt,int pos,long long k){//单点赋值 
        if(l==r){
            mx[rt]=k;
            return;
        }
        push_down(rt);
        int mid=(l+r)>>1;
        if(pos<=mid)modify2(Lson,pos,k);
        if(pos>mid)modify2(Rson,pos,k);
        mx[rt]=max(mx[Ls],mx[Rs]);
    }
}t1,t2;

I long long get_d(int x){//得到x这个点当前的带权深度 //所以还是多整点小函数方便啊hhh 
    return  t1.query(Root,dfn[x],dfn[x]);
}

I int ed(int x){return dfn[x]+siz[x]-1;}//x子树dfs序最靠右的点 

I long long get_d2(int x,int v){//得到x除了v这个儿子，之外的子树，带权深度的最大值 
    return max(t1.query(Root,dfn[x],dfn[v]-1),t1.query(Root,ed(v)+1,ed(x))); 
}

I long long get_ans(int u){
    long long anss=0;
    long long dep_u=get_d(u);//u目前的带权深度 
    int x=u;

    while(x){//还没跳到祖先 
//      cout<<"x"<<x<<endl;
        int tpp=top[x];
        anss=max(anss,dep_u+t2.query(Root,dfn[tpp],dfn[x]-1));//别忘了top[u]在上面
        //为啥这里dfn[x]要-1呢？因为此时x在链的底端，它就是上一次走到的“轻边上端的点”，不能统计它的dep[v]-2*dep[x] 
        //但这样就会丢失u向下走的答案，需要最后统计一下。
        int ftp=fa[tpp];
        if(!ftp)break;//啊，得判掉。。 
        anss=max(anss,dep_u+get_d2(ftp,tpp)-get_d(ftp)*2);
        x=ftp;
    }
    anss=max(anss,t1.query(Root,dfn[x],ed(x))-dep_u);

    return anss;
} 

I void Modify(int u){
    int x=u;
    while(x){
        int tpp=top[x],ftp=fa[tpp];
        if(!ftp)break;
        long long val=get_d2(ftp,mson[ftp])-2*get_d(ftp);
        t2.modify2(Root,dfn[ftp],val);
        x=ftp;
    }
}

int main(){
//  freopen("ex_road2.in","r",stdin);//终于过了大样例，赶紧交上去，0pts，心态崩了，然后发现没关文件hhh 
//  freopen("zj.out","w",stdout); 
    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int u=read(),v=read(),w=read();
        insert(u,v,w);
        insert(v,u,w);
    }
    dfs1(1,0,0);
    dfs2(1,1);
    t1.build(Root,depth);
    t2.build(Root,ww);

    for(int i=1;i<=m;i++){
        if(read()==1){//查询操作，查u到所有点距离的最大值。 
            printf("%lld\n",get_ans(read()));  
        }
        else{
            //对于<u,v>这条边，设u在下，变大了d
//          要改两部分：t1的u子树（包括u），它们的深度都会增加d
//          t2：1.u子树内，看看dep[v]-2*dep[x]就可以看出，因为dep[v],dep[x]都变大了d，因此u子树内所有点的值都会-d 
//              2.u往上到根路径上，每条轻边靠上的点，它的值会改变；直接利用t1的信息重新计算即可。
            int ee=read();int u=edge[(ee<<1)-1].to,v=edge[(ee<<1)].to,org=edge[ee<<1].dis;//org是原来的值 
            if(dep[u]<dep[v])u^=v^=u^=v;
            int ww=read();
            t1.modify1(Root,dfn[u],ed(u),ww-org);//1.1 
            t2.modify1(Root,dfn[u],ed(u),org-ww);//2.1
            Modify(u);//修改u向上路径上轻边靠上的点的权值（u也可能被修改）//2.2
            edge[ee<<1].dis=ww,edge[(ee<<1)-1].dis=ww;//居然往把这个改了hhh太傻了，，还是拍了拍才发现/哭泣 
//          printf("%lld\n",get_d(7));
        }
    }
    return 0;
}

动态维护直径的做法

#include<algorithm>
#include<iostream>
#include<cstdio>
#define INF 0x3f3f3f3f3f3f3f3f
#define I inline
#define RR register
#define Root 1,n,1
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
#define Ls rt<<1
#define Rs rt<<1|1 
#define lowbit(x) (x&-x)
using std::cout;
using std::endl;
using std::max;
using std::min;

int read(){
    int h=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+c-'0',c=getchar();
    return h;
}

//longlong 
const int MAXN=404000; 
int n,m;

struct Edge{
    int to;
    int nxt;
    int dis; 
}edge[MAXN];
int frm[MAXN];
int cnt_e;

void insert(int u,int v,int w){
    cnt_e++;
    edge[cnt_e].to=v;
    edge[cnt_e].nxt=frm[u];
    edge[cnt_e].dis=w;
    frm[u]=cnt_e;
}

int dfn[MAXN],id[MAXN],cnt_d;
int dep[MAXN];//真实深度 
long long depth[MAXN];//带权深度 
int siz[MAXN]; 
int f[MAXN>>1][19];

void dfs(int x,int fa,int w){
    dfn[x]=++cnt_d;id[cnt_d]=x; 
    f[x][0]=fa;
    siz[x]=1;
    for(int i=1;i<=15;i++)f[x][i]=f[f[x][i-1]][i-1];
    dep[x]=dep[fa]+1,depth[x]=depth[fa]+w;
    for(int i=frm[x];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v!=fa)dfs(v,x,edge[i].dis),siz[x]+=siz[v];//我窒息了，，这写成了dfs(v,x,edge[i].to)（*&%7W%&*(^ 
    }
}

struct BIT{//树状数组对dfs维护深度，支持区间加，单点查询（线段树常数有点太自闭。。 
    long long z[MAXN];

    void modify(int x,long long k){//如果是x==n+1的话，它压根不会进这个循环  
        for(int i=x;i<=n;i+=lowbit(i)){
            z[i]+=k;
        }
    }

    long long query(int x){
        long long anss=0;
        for(int i=x;i;i-=lowbit(i)){
            anss+=z[i];
        }
        return anss;
    }
}t1;

int get_lca(int x,int y){
    if(dep[x]>dep[y])x^=y^=x^=y;
    for(int i=15;i>=0;i--){//啊这常数太窒息了吧 
        if(dep[f[y][i]]>=dep[x])
            y=f[y][i];
    }
    if(x==y)return x;
    for(int i=15;i>=0;i--){
        if(f[y][i]!=f[x][i]){
            y=f[y][i],x=f[x][i];
        }
    } 
    return f[y][0];
}

I long long get_d(int x){return t1.query(dfn[x]);}//别忘了转dfs序 

long long get_dis(int x,int y){//得到原编号为x,y的点的距离 
    int lca=get_lca(x,y);
    return get_d(x)+get_d(y)-2*get_d(lca); 
}

bool ch_ck(int L,int R,int l,int r){//[L,R]，[l,r]有交集，并且交不为[L,R] 
    if(l<=L&&R<=r)return false;
    if(R<l||L>r)return false; 
    return true;
}

struct Segmen_Tree2{//对dfs序维护直径 
    int u[MAXN<<3],v[MAXN<<3];//直径俩端点的原编号 

    void update(int rt){
        int pt[4];
        pt[0]=u[Ls],pt[1]=v[Ls],pt[2]=u[Rs],pt[3]=v[Rs];//常数有点窒息啊。。
        long long mxn=-1;//边权有0！！！！ 
        for(int i=0;i<=2;i++){
            for(int j=i+1;j<=3;j++){
                long long hh=get_dis(pt[i],pt[j]);
                if(hh>mxn){
                    mxn=hh;
                    u[rt]=pt[i],v[rt]=pt[j];
                }
            }
        } 
//      cout<<rt<<":";for(int i=0;i<=3;i++)cout<<pt[i]<<' ';puts("");
//      cout<<"ANS:"<<u[rt]<<' '<<v[rt]<<endl;
    }

    void build(int l,int r,int rt){
        if(l==r){
            u[rt]=v[rt]=id[l];
            return; 
        }
        int mid=(l+r)>>1;
        build(Lson);build(Rson);
        update(rt);
    } 

    void modify(int l,int r,int rt,int x,int y){//修改了连接xy两点边的边权。 
//      cout<<l<<' '<<r<<' '<<id[l]<<' '<<id[r]<<' '<<x<<' '<<x+siz[id[x]]-1<<endl;
        if(l==r)return;
        if(ch_ck(l,r,x,x+siz[id[x]]-1)==false){
            return;
        }
        int mid=(l+r)>>1;
        modify(Lson,x,y);modify(Rson,x,y);
        update(rt);
//      cout<<l<<' '<<r<<' '<<id[l]<<' '<<id[r]<<' '<<u[rt]<<' '<<v[rt]<<endl;
    }
}t2;

long long get_ans(int x){
    long long anss=max(get_dis(x,t2.u[1]),get_dis(x,t2.v[1]));
    return anss;
} 

int main(){
//  freopen("ex_road2.in","r",stdin);//终于过了大样例，赶紧交上去，0pts，心态崩了，然后发现没关文件hhh 
//  freopen("zj.out","w",stdout); 
    n=read(),m=read();
    for(int i=1;i<=n-1;i++){
        int u=read(),v=read(),w=read();
        insert(u,v,w);
        insert(v,u,w);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++){
        t1.modify(dfn[i],depth[i]);
        t1.modify(dfn[i]+1,-depth[i]);
    }
    t2.build(Root);
    for(int i=1;i<=m;i++){
        if(read()==1){
            printf("%lld\n",get_ans(read()));
        }
        else{
            int ee=read(),ww=read();
            int u=edge[ee<<1].to,v=edge[(ee<<1)-1].to;int org=edge[ee<<1].dis;
            if(dep[u]<dep[v])u^=v^=u^=v;
            t1.modify(dfn[u],ww-org);t1.modify(dfn[u]+siz[u],-(ww-org));//深度要修改的就是u子树内的信息。
            t2.modify(Root,dfn[u],dfn[v]);
            edge[ee<<1].dis=ww,edge[(ee<<1)-1].dis=ww;
//          cout<<t2.u[1]<<' '<<t2.v[1]<<endl;
        }
    }
    return 0;
}