EOJ 306 树上问题

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题解：

因为w大于1，所以，题意就是，有多少(x,z)，存在x到z的路径上，有一个x<y<z的y

w没用的其实。

树上路径问题，有什么方法吗？

1.树链剖分。这个主要方便处理修改操作。

2.点分治，对于静态无修改点树上统计，非常好用。

3.一些其他的：

利用lca，dfs序，判断点在路径上，点在子树里一些情况。

倍增，处理fa[N][20]，dis[N][20] ，

二分再套一个倍增？

4.还有一些灵活应变的：

例如：拆路径为x到lca，lca到y，可以在x，y记录一些lca的信息，把路径就变成了点。

例题：牛客网NOIP赛前集训营-提高组（第一场）T3

这个题，静态无修树上统计，就点分治了。

还可以再带一个log

那么当前层的重心G，统计过G路径。

树形背包思想，直接统计z能和之前的那些x凑成点对，记录x到G路径上的大于x最小的编号nx（因为是存在，不是任意嘛）

然后记录z到G路径上小于z的最大编号pz

如果pz>x，那么可以

如果nx<y，那么可以

但是pz<nx的情况被算重了。去重要用二维数据结构两个log就TLE了。

正难则反。考虑所有的点对。C（n,2）

对于x到z路径上都比x，z小的去掉，都比x、z大的去掉。就可以了。

具体来说，维护一个树状数组，

以去掉路径上都比x、z小的为例：

之前访问的作为x，如果x到根节点的路径上（包括根）最大值（不存在就是一个任意问题了）小于x，把x位置++

dfs统计，对于z，如果G到z路径上的最大值mx小于z，统计query(z-1)-query(mx)

表示得到编号在mx+1到z-1的x，且x到根路径上的最大值小于x的x数量。

就可以去掉这部分。

当然，因为G儿子的循环顺序，必须正序循环一遍，再倒序循环一遍。当前都作为z，之前的作为x，一定不会漏

另一个都比x，z大的同理。

而且之后统计路径上比x、z都大的情况不会算重。

小细节：

1.C(n,2)会爆int

2.子树的sz不是开始统计的sz，递归之前，必须从新的根即重心G再dfs统计sz

3.点分治一定要时刻控制：if(vis[e[i].to]) continue 否则T得飞起，WA的痛快。

4.发现，对于每条边的两端点对，会被减掉两次。

所以，ans开始还要加上(n-1)

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=+;

const int inf=0x3f3f3f3f;

ll n;

int rt,nowsz;

bool vis[N];

int mxsz[N],sz[N];

int f[N];

void add(int x,int c){//树状数组

    for(;x<=n;x+=x&(-x)) f[x]+=c;

}

int query(int x){

    int ret=;for(;x;x-=x&(-x)) ret+=f[x];return ret;

}

int sta[N],top;

int mxid[N],miid[N];//路径上编号最小值，最大值

ll ans;

struct node{

    int nxt,to;

    int pre;

}e[*N];

int hd[N],cnt;

int las[N];

void con(int x,int y){//注意建立双向邻接表，便于反过来dfs

    if(hd[x]&&e[hd[x]].nxt==) las[x]=hd[x];

    e[++cnt].nxt=hd[x];

    e[hd[x]].pre=cnt;

    e[cnt].to=y;

    hd[x]=cnt;

}

void dfs0(int x,int fa){//dfs0找根

    sta[++top]=x;

    mxid[x]=;mxsz[x]=;

    miid[x]=;

    sz[x]=;

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        dfs0(y,x);

        sz[x]+=sz[y];

        mxsz[x]=max(mxsz[x],sz[y]);

    }

    if(mxsz[x]<=nowsz/&&(nowsz-sz[x])<=nowsz/) rt=x;

}

void fsz(int x,int fa){//找完rt更新sz

    sz[x]=;

    for(int i=hd[x];i;i=e[i].nxt){

        if(vis[e[i].to]) continue;

        if(e[i].to!=fa){

            fsz(e[i].to,x);

            sz[x]+=sz[e[i].to];

        }

    }

}

void dfs1(int x,int mx,int fa){//dfs1统计答案，对于路径上的点都比x，z小的。

    mxid[x]=mx;

    if(mx<x) ans-=(query(x-)-query(mx));

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        dfs1(y,max(mx,x),x);

    }

}

void upda1(int x,int fa){//dfs1之后，更新子树

    if(mxid[x]<x) add(x,);

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        upda1(y,x);

    }

}

void srt1(int x,int fa,int mx){//根比较麻烦，单独处理

    //if(mx<rt&&x>rt) ans--;

    if(mx<rt&&x>mx) ans--;

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        srt1(y,x,max(mx,x));

    }

}

void dvi1(int in){//点分治1

    dfs0(in,);

    fsz(rt,);

    for(int i=hd[rt];i;i=e[i].nxt){

        if(vis[e[i].to]) continue;

        dfs1(e[i].to,rt,rt);

        upda1(e[i].to,rt);

    }

    for(int i=;i<=top;i++){

        int x=sta[i];

        if(x==rt) continue;

        if(mxid[x]<x) add(x,-);

    }

    for(int i=las[rt];i;i=e[i].pre){//反向再处理一次

        if(vis[e[i].to]) continue;

        dfs1(e[i].to,rt,rt);

        upda1(e[i].to,rt);

    }

    for(int i=hd[rt];i;i=e[i].nxt){

        if(vis[e[i].to]) continue;

        srt1(e[i].to,rt,);

    }

    while(top){

        int x=sta[top--];

        if(x==rt) continue;

        if(mxid[x]<x) add(x,-);

    }

    vis[rt]=;

    for(int i=hd[rt];i;i=e[i].nxt){

        int y=e[i].to;

        if(vis[y]) continue;

        nowsz=sz[y];

        dvi1(y);

    }

}

//以下是x，z路径上点都比较大的，同理

void dfs2(int x,int mi,int fa){

    miid[x]=mi;

    if(mi>x) ans-=(query(mi-)-query(x));

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        dfs2(y,min(mi,x),x);

    }

}

void upda2(int x,int fa){

    if(miid[x]>x) add(x,);

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        upda2(y,x);

    }

}

void srt2(int x,int fa,int mi){

    if(mi>rt&&x<mi) ans--;

    for(int i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa) continue;

        if(vis[y]) continue;

        srt2(y,x,min(mi,x));

    }

}

void dvi2(int in){

    dfs0(in,);

    fsz(rt,);

    for(int i=hd[rt];i;i=e[i].nxt){

        if(vis[e[i].to]) continue;

        dfs2(e[i].to,rt,rt);

        upda2(e[i].to,rt);

    }

    for(int i=;i<=top;i++){

        int x=sta[i];

        if(x==rt) continue;

        if(miid[x]>x) add(x,-);

    }

    for(int i=las[rt];i;i=e[i].pre){

        if(vis[e[i].to]) continue;

        dfs2(e[i].to,rt,rt);

        upda2(e[i].to,rt);

    }

    for(int i=hd[rt];i;i=e[i].nxt){

        if(vis[e[i].to]) continue;

        srt2(e[i].to,rt,inf);

    }

    while(top){

        int x=sta[top--];

        if(x==rt) continue;

        if(miid[x]>x) add(x,-);

    }

    vis[rt]=;

    for(int i=hd[rt];i;i=e[i].nxt){

        int y=e[i].to;

        if(vis[y]) continue;

        nowsz=sz[y];

        dvi2(y);

    }

}

int main(){

    scanf("%lld",&n);

    int x,y,z;

    for(int i=;i<=n-;i++){

        scanf("%d%d%d",&x,&y,&z);

        con(x,y);con(y,x);

    }

    ans=(n-)*n/ + (n-);//warning warning warning!!!

    nowsz=n;

    dvi1();

    memset(vis,,sizeof vis);//解开封锁

    top=;

    nowsz=n;

    dvi2();

    printf("%lld",ans);

    return ;

}