洛谷2543AHOI2005]航线规划（树剖+线段树+割边思路）

这个题的思路还是比较巧妙的。

首先，我们发现操作只有删除和询问两种，而删除并不好维护连通性和割边之类的信息。

所以我们不妨像WC2006水管局长那样，将询问离线，然后把操作转化成加边和询问。

然后，我们会发现，若存在一条边\(x->y\)，那么原本x到y的所有割边，都会变成非割边。

那意味着什么呢？

似乎加边操作，可以直接转化成区间修改。

那我们就可以首先对不涉及删除边，建一个生成树。（题目保证一定合法）

那么对于一棵树，所有的边都是割边，所以一开始所有的边的边权都是1（这里为了修改方便，我们将边权直接转化成点权了），也就是说树上除了根以外，权值都是1.

然后依次插入那些没有被删除，但是没有在生成树里面的边。每插入一条边，就涉及到一次链修改，将一条链的点的权值变成\(0\)。

然后操作中的加边也是同理。

对于询问的话，直接询问\((x,y)\)的路径和就好。

但是有一个需要注意的地方就是。由于我们边权转点权，所以\(lca\)处的点不属于路径，修改和询问的时候都需要注意的。

有些细节直接看代码吧

#include<bits/stdc++.h>

#define mk make_pair

#define pb push_back

#define ll long long

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 2e5+1e2;

const int maxm = 2*maxn;

struct Node{

    int opt,x,y;

};

Node a[maxm];

int f[4*maxn];

int add[4*maxn];

int n,m,fa[maxn];

int dfn[maxn],size[maxn],newnum[maxn],deep[maxn];

int top[maxn],son[maxn];

int point[maxn],nxt[maxm],to[maxm];

int in[maxn],tag[maxn];

int newval[maxn];

map<pair<int,int>,int> mp;

int cnt;

void addedge(int x,int y)

{

    nxt[++cnt]=point[x];

    to[cnt]=y;

    point[x]=cnt;

}

void dfs(int x,int faa,int dep)

{

    deep[x]=dep;

    size[x]=1;

    int maxson = -1;

    for (int i=point[x];i;i=nxt[i])

    {

        int p = to[i];

        if (p==faa) continue;

        fa[p]=x;

        dfs(p,x,dep+1);

        size[x]+=size[p];

        if (size[p]>maxson)

        {

            maxson=size[p];

            son[x]=p;

        }

    }

}

int tot;

void dfs1(int x,int chain)

{

   newnum[x]=++tot;

   //cout<<x<<" "<<tot<<"****"<<endl;

   newval[tot]=1;

   top[x]=chain;

   if (!son[x]) return;

   dfs1(son[x],chain);

   for (int i=point[x];i;i=nxt[i])

   {

   	int p = to[i];

   	if(!newnum[p])

   	{

   		dfs1(p,p);

       }

   }

}

void up(int root)

{

    f[root]=f[2*root]+f[2*root+1];

}

void pushdown(int root,int l,int r)

{

    if (add[root]!=-1)

    {

        add[2*root]=add[root];

        add[2*root+1]=add[root];

        int mid = l+r >> 1;

        f[2*root]=(mid-l+1)*add[root];

        f[2*root+1]=(r-mid)*add[root];

        add[root]=-1;

    }

}

void build(int root,int l,int r)

{

    add[root]=-1;

    if(l==r)

    {

        f[root]=newval[l];

        return;

    }

    int mid = l+r >> 1;

    build(2*root,l,mid);

    build(2*root+1,mid+1,r);

    up(root);

}

void update(int root,int l,int r,int x,int y,int p)

{

    if (x<=l && r<=y)

    {

        add[root]=p;

        f[root]=(r-l+1)*p;

        return;

    }

    pushdown(root,l,r);

    int mid = l+r >> 1;

    if (x<=mid) update(2*root,l,mid,x,y,p);

    if (y>mid) update(2*root+1,mid+1,r,x,y,p);

    up(root);

}

int query(int root,int l,int r,int x,int y)

{

    if (x<=l && r<=y)

    {

        return f[root];

    }

    pushdown(root,l,r);

    int mid = l+r >> 1;

    int ans = 0;

    if (x<=mid) ans=ans+query(2*root,l,mid,x,y);

    if (y>mid) ans=ans+query(2*root+1,mid+1,r,x,y);

    return ans;

}

void treeadd(int x,int y,int z)

{

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        update(1,1,n,newnum[top[x]],newnum[x],z);

        x=fa[top[x]];

    }

    if (deep[x]>deep[y]) swap(x,y);

    int pre = query(1,1,n,newnum[x],newnum[x]);

    update(1,1,n,newnum[x],newnum[y],z);

    update(1,1,n,newnum[x],newnum[x],pre);

}

int treesum(int x,int y)

{

    int ans=0;

    while (top[x]!=top[y])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        ans=ans+query(1,1,n,newnum[top[x]],newnum[x]);

        x=fa[top[x]];

    }

    if (deep[x]>deep[y]) swap(x,y);

    int pre = query(1,1,n,newnum[x],newnum[x]);

    ans=ans+query(1,1,n,newnum[x],newnum[y]);

    ans-=pre;

    return ans;

}

int x[maxm],y[maxm];

int ffa[maxn];

int ans[maxm];

int find(int x)

{

    if (ffa[x]!=x) ffa[x]=find(ffa[x]);

    return ffa[x];

}

int main()

{

  n=read(),m=read();

  for (int i=1;i<=n;i++) ffa[i]=i;

  for (int i=1;i<=m;i++)

  {

  	 x[i]=read(),y[i]=read();

  	 mp[mk(x[i],y[i])]=mp[mk(y[i],x[i])]=i;

  }

  int tmp=0;

  while (1)

  {

  	int opt=read();

  	if(opt==-1) break;

  	a[++tmp].opt=opt;

  	a[tmp].x=read();

  	a[tmp].y=read();

  }

  for (int i=1;i<=tmp;i++) if (a[i].opt==0) tag[mp[mk(a[i].x,a[i].y)]]=1;

  for (int i=1;i<=m;i++)

  {

  	if (tag[i]) continue;

  	int f1=find(x[i]);

  	int f2=find(y[i]);

  	if (f1==f2) continue;

  	ffa[f1]=f2;

  	addedge(x[i],y[i]);

  	addedge(y[i],x[i]);

  	in[i]=1;

  }

  dfs(1,0,1);

  dfs1(1,1);

  newval[1]=0;

  build(1,1,n);

  int tmp1=0;

  for (int i=1;i<=m;i++)

  {

  	if (tag[i] || in[i]) continue;

  	treeadd(x[i],y[i],0);

  }

  for (int i=tmp;i>=1;i--)

  {

  	 if (a[i].opt==0)

  	 {

  	 	treeadd(a[i].x,a[i].y,0);

     }

     else

     {

     	ans[++tmp1]=treesum(a[i].x,a[i].y);

     }

  }

  for (int i=tmp1;i>=1;i--)

  {

  	cout<<ans[i]<<"\n";

  }

  return 0;

}

巴特西

洛谷2543AHOI2005]航线规划（树剖+线段树+割边思路）

最新文章

热门文章

巴特西

洛谷2543AHOI2005]航线规划 （树剖+线段树+割边思路）

最新文章

热门文章

洛谷2543AHOI2005]航线规划（树剖+线段树+割边思路）