Description
如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的 核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力 之下。 小强建立了一个模型。这世界上有N个网络设备,他们之间有M个双向的 链接。这个世界是连通的。在一段时间里,有Q个数据包要从一个网络设备发 送到另一个网络设备。 一个网络设备承受的压力有多大呢?很显然,这取决于Q个数据包各自走 的路径。不过,某些数据包无论走什么路径都不可避免的要通过某些网络设 备。 你要计算:对每个网络设备,必须通过(包括起点、终点)他的数据包有 多少个?
对于40%的数据,N,M,Q≤2000 对于60%的数据,N,M,Q≤40000 对于100%的数据,N≤100000,M,Q≤200000
Solution
一开始写了缩点发现这样不太好做。。 考虑建广义圆方树，路径上的必经点显然是树上路径中的圆点 由于做了很多天的树链剖分模拟赛已经吐了，我们今天用差分的做法。 对于一条路径修改(x,y)，我们在x、y处+1，在lca和fa[lca]处-1，然后离线求和即可 好像没啥好说的。。。
Code
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stack>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
const int N
=200005;
std
:: stack
<int> stack
;
struct Graph
{
struct edge
{int y
,next
;} e
[N
*2];
int ls
[N
],edCnt
;
Graph() {fill(ls
,0); edCnt
=1;}
edge
operator [](int x
) const {
return e
[x
];
}
void add_edge(int x
,int y
) {
e
[++edCnt
]=(edge
) {y
,ls
[x
]}; ls
[x
]=edCnt
;
e
[++edCnt
]=(edge
) {x
,ls
[y
]}; ls
[y
]=edCnt
;
}
} G
,T
;
int bl
[N
],size
[N
],fa
[N
],dep
[N
];
int dfn
[N
],low
[N
];
int s
[N
],tot
;
bool vis
[N
];
int read() {
int x
=0,v
=1; char ch
=getchar();
for (;ch
<'0'||ch
>'9';v
=(ch
=='-')?(-1):(v
),ch
=getchar());
for (;ch
<='9'&&ch
>='0';x
=x
*10+ch
-'0',ch
=getchar());
return x
*v
;
}
void dfs(int now
,int from
) {
dfn
[now
]=low
[now
]=++dfn
[0]; vis
[now
]=true;
for (int i
=G
.ls
[now
];i
;i
=G
[i
].next
) {
if ((i
^1)==from
) continue;
if (!dfn
[G
[i
].y
]) {
stack
.push(i
); dfs(G
[i
].y
,i
);
low
[now
]=std
:: min(low
[now
],low
[G
[i
].y
]);
if (dfn
[now
]<=low
[G
[i
].y
]) {
int y
=0; tot
++;
while (y
!=i
) {
y
=stack
.top(); stack
.pop();
T
.add_edge(tot
,G
[y
].y
);
}
T
.add_edge(now
,tot
);
}
} else if (vis
[G
[i
].y
]) low
[now
]=std
:: min(low
[now
],dfn
[G
[i
].y
]);
}
vis
[now
]=false;
}
void dfs1(int now
) {
size
[now
]=1;
for (int i
=T
.ls
[now
];i
;i
=T
[i
].next
) {
if (T
[i
].y
==fa
[now
]) continue;
fa
[T
[i
].y
]=now
; dep
[T
[i
].y
]=dep
[now
]+1;
dfs1(T
[i
].y
);
size
[now
]+=size
[T
[i
].y
];
}
}
void dfs2(int now
,int up
) {
bl
[now
]=up
; int mx
=0;
for (int i
=T
.ls
[now
];i
;i
=T
[i
].next
) {
if (T
[i
].y
!=fa
[now
]&&size
[T
[i
].y
]>size
[mx
]) mx
=T
[i
].y
;
}
if (!mx
) return ;
dfs2(mx
,up
);
for (int i
=T
.ls
[now
];i
;i
=T
[i
].next
) {
if (T
[i
].y
!=fa
[now
]&&T
[i
].y
!=mx
) dfs2(T
[i
].y
,T
[i
].y
);
}
}
int get_lca(int x
,int y
) {
for (;bl
[x
]!=bl
[y
];) {
(dep
[bl
[x
]]<dep
[bl
[y
]])?(std
:: swap(x
,y
)):(void)0;
x
=fa
[bl
[x
]];
}
return dep
[x
]<dep
[y
]?x
:y
;
}
void dfs3(int now
) {
for (int i
=T
.ls
[now
];i
;i
=T
[i
].next
) {
if (T
[i
].y
==fa
[now
]) continue;
dfs3(T
[i
].y
);
s
[now
]+=s
[T
[i
].y
];
}
}
int main(void) {
int n
=read(),m
=read(),q
=read(); tot
=n
;
rep(i
,1,m
) G
.add_edge(read(),read());
dfs(1,0);
dfs1(1); dfs2(1,1);
rep(i
,1,q
) {
int x
=read(),y
=read();
int lca
=get_lca(x
,y
);
s
[x
]++; s
[y
]++;
s
[lca
]--; s
[fa
[lca
]]--;
}
dfs3(1);
rep(i
,1,n
) printf("%d\n", s
[i
]);
return 0;
}
