P2542 [AHOI2005] 航线规划

题意描述:

洛谷

有 一个 \(n\) 个点 \(m\) 条边的无向图,还有若干个操作。定义 \(u,v\) 的关键路径为删除这条边之后, \(u,v\) 不连通的边。

  • 操作1: 询问 \(u\) 和 \(v\) 之间的关键路径的个数。
  • 操作2: 断开 \(u\) 和 \(v\) 之间的边。

保证任意时刻两点之间都能互相到达。

数据范围: \(n\leq 3e4,m\leq 10^5,q\leq 4e4\)

solution

蒟蒻只会离线的做法,在线的 \(LCT\) 做法 没学会(淦)。

每次删边我们在线的话不太好操作,考虑离线一下。

因为题目保证了任意时刻两点之间都是互相到达的,所以我们最后一定能构成一棵树和一些非树边。

我们先从没被摧毁的边中选出 \(n-1\) 条边出来构成一棵树, 然后问题就转化为了树上问题。

对于一棵树来说,任意两点之间的关键路径的个数就是两点之间的距离。

考虑在之后的加边过程中,节点 \(u\) 和 \(v\) 之间连了一条边,那么 树上 \(u-v\) 这一条路径上的边肯定不会成为关键路径。

举个例子:

P2542 [AHOI2005] 航线规划

节点 \(2\) 和 \(3\) 之间连了一条非树边,那么 \(1,2,3\) 这三个节点之间,任意两个点之间都有两条路径,所以 \(2-3\) 这一条路径上 的边一定不会是关键路径。

树上路径赋零,路径求和,树剖加线段树即可。

注意: 一开始还应该统计一下没被删除的非树边的贡献。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e5+10;
int n,m,tot,num,cnt,opt;
int head[N],dfn[N],siz[N],son[N],fa[N],top[N],dep[N],u[N],v[N];
map<pair<int,int>,int> id;
bool vis[N];
struct node
{
    int to,net,id;
}e[N<<1];
struct QAQ
{
    int opt,u,v,ans;
}q[N<<1];
struct Tree
{
    int lc,rc,tag,sum;
}tr[N<<2];
#define l(o) tr[o].lc
#define r(o) tr[o].rc
#define tag(o) tr[o].tag
#define sum(o) tr[o].sum
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w; 
}
void add(int x,int y,int z)
{
    e[++tot].to = y;
    e[tot].id = z;
    e[tot].net = head[x];
    head[x] = tot;
}
void get_tree(int x)
{
    dep[x] = dep[fa[x]] + 1; siz[x] = 1;
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa[x] || dep[to] || vis[e[i].id]) continue;
        fa[to] = x;
        get_tree(to);
        siz[x] += siz[to];
        if(siz[to] > siz[son[x]]) son[x] = to;
    }
}
void dfs(int x,int topp)
{
	top[x] = topp; dfn[x] = ++num;
    if(son[x]) dfs(son[x],topp); 
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(to == fa[x] || to == son[x] || vis[e[i].id] || fa[to] != x) continue;
        dfs(to,to);
    }
}
void cover(int o)
{
    tag(o) = 1;
    sum(o) = 0;
}
void down(int o)
{
    if(tag(o))
    {
        cover(o<<1);
        cover(o<<1|1);
        tag(o) = 0;
    }
}
void up(int o)
{
    sum(o) = sum(o<<1) + sum(o<<1|1);
}
void build(int o,int L,int R)
{
    l(o) = L, r(o) = R;
    if(L == R)
    {
        sum(o) = 1;
        return;
    }
    int mid = (L + R)>>1;
    build(o<<1,L,mid);
    build(o<<1|1,mid+1,R);
    up(o);
}
void chenge(int o,int L,int R)
{
	if(L <= l(o) && R >= r(o))
    {
        cover(o);
        return;
    }
    down(o);
    int mid = (l(o) + r(o))>>1;
    if(L <= mid) chenge(o<<1,L,R);
    if(R > mid) chenge(o<<1|1,L,R);
    up(o);
}
int query(int o,int L,int R)
{
    int res = 0;
    if(L <= l(o) && R >= r(o)) return sum(o);
    down(o);
    int mid = (l(o) + r(o))>>1;
    if(L <= mid) res += query(o<<1,L,R);
    if(R > mid) res += query(o<<1|1,L,R);
    return res;
}
void modify(int x,int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] <= dep[top[y]]) swap(x,y);
        chenge(1,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] >= dep[y]) swap(x,y);
    chenge(1,dfn[x]+1,dfn[y]);
}
int ask(int x,int y)
{
    int res = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] <= dep[top[y]]) swap(x,y);
        res += query(1,dfn[top[x]],dfn[x]);
        x = fa[top[x]];
    }
    if(dep[x] >= dep[y]) swap(x,y);
    res += query(1,dfn[x]+1,dfn[y]);
    return res;
}
void DFS(int x)//找没被删除非树边
{
	for(int i = head[x]; i; i = e[i].net)
	{
		int to = e[i].to;
		if(to == fa[x] || vis[e[i].id]) continue;
		if(fa[to] == x) DFS(to);
		else modify(to,x);	
	}
}
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        u[i] = read(); v[i] = read();
        id[make_pair(u[i],v[i])] = i;
        add(u[i],v[i],i); add(v[i],u[i],i);
    }
    while(1)
    {
        opt = read();
        if(opt == -1) break;
        q[++cnt].opt = opt;
        q[cnt].u = read();
        q[cnt].v = read();
        if(q[cnt].opt == 0) vis[id[make_pair(q[cnt].u,q[cnt].v)]] = 1;
    }    
	get_tree(1); dfs(1,1); build(1,1,n); DFS(1);
    for(int i = cnt; i >= 1; i--)
    {
        if(q[i].opt == 0) modify(q[i].u,q[i].v);
        else q[i].ans = ask(q[i].u,q[i].v);
    }
    for(int i = 1; i <= cnt; i++) if(q[i].opt == 1) printf("%d\n",q[i].ans);
    return 0;
}
上一篇:OAuth 2.0的一个简单解释


下一篇:利用vue-meta管理头部标签