P7924
0xFF
·
·
题解
题目大意
给定一个有 n 个点 m 条边的无向图，每个点有一个点权。有 q 组询问，每次询问顶点 x 到顶点 y 之间的所有非严格简单路径所包含的点权值之和，每个点权值只会被计算一次。
题目分析
根据题目描述，每个点权只会被累加一次，故我们可以处理出总共有多少个点在所有的询问中被覆盖，计算出这些点的权值之和即可。
首先考虑如何在时间范围内实现每个点只被累加一次。
以样例为例：
三次询问共覆盖了 1,2,3,4 这 4 个点，故答案为 10。
考虑第一组询问 1 2 从 1 到 2 共有两条路径，分别是 1→2 与
经过这样操作之后，整张图上就没有环了，那么必然形成一棵树。题目中要求两个顶点之间的点权和，可以通过树上差分解决。
树上差分是利用两点的最近公共祖先为中转点来维护某一点经过的次数。
在本题中，我们利用树上差分维护操作完成后至少被经过一次的点的点权和。
#### 代码实现
------------
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(; isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
const int N=5000050;
const int M=5050;
int n,m,a[N],Vis[N],tot,dfn[N],low[N],stk[N],sc,Belong[N],Sum[N],t,cnt;
int pre[N],Size[N],depth[N],fa[N],son[N],Tot,head[N],Head[N],top[N];
bool vis[N];
int Cnt,Q;
struct node{
int u,v,nxt;
}edge[N],E[N];
void Add_edge(int u,int v){
edge[++cnt].u=u;
edge[cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
void Add(int u,int v){
E[++Cnt].v=v;
E[Cnt].u=u;
E[Cnt].nxt=Head[u];
Head[u]=Cnt;
}
int dep[N],f[N][21];
void dfs(int now,int fath){
dep[now]=dep[fath]+1;
f[now][0]=fath;
for(int i=1;(1<<i)<=dep[now];i++){
f[now][i]=f[f[now][i-1]][i-1];
}
for(int i=Head[now];i;i=E[i].nxt){
if(E[i].v != fath) dfs(E[i].v,now);
}
}
int LCA(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
for(int i=20;i>=0;i--)
if(dep[x]+(1<<i)<=dep[y])
y=f[y][i];
if(x==y) return x;
for(int i=20;i>=0;i--){
if(f[x][i]==f[y][i]) continue;
else{
y=f[y][i];
x=f[x][i];
}
}
return f[x][0];
}
void tarjan(int now,int fath){
low[now]=dfn[now]=++tot;
stk[++sc]=now;vis[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].v;
if(!dfn[to]) tarjan(to,now),low[now]=min(low[now],low[to]);
else if(vis[to]&&to!=fath) low[now]=min(low[now],dfn[to]);
}
if(dfn[now]==low[now]){
int pre=stk[sc--];
Sum[++t]+=a[pre];
Belong[pre]=t;vis[pre]=0;
while(pre!=now){
pre=stk[sc--],Sum[t]+=a[pre];
Belong[pre]=t;vis[pre]=0;
}
}
}
long long Ans;
void Dfs(int now,int fath){
for(int i=Head[now];i;i=E[i].nxt){
if(E[i].v != fath) Dfs(E[i].v,now),
Vis[now] += Vis[E[i].v];
}
if(Vis[now]) Ans+=Sum[now];
}
signed main() {
n=read(); m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1,u,v;i<=m;i++){
u=read();v=read();
Add_edge(u,v);Add_edge(v,u);
}
Q=read();
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
for(int i=1;i<=cnt;i+=2){
if(Belong[edge[i].u]^Belong[edge[i].v]){
Add(Belong[edge[i].u],Belong[edge[i].v]);
Add(Belong[edge[i].v],Belong[edge[i].u]);
}
}
memset(dfn,0,sizeof dfn);
for(int i=1;i<=Q;i++){
int u=read(),v=read();
int Lca=LCA(Belong[u],Belong[v]);
Vis[Belong[u]]++;Vis[Belong[v]]++;
Vis[Lca]--;
Vis[fa[Lca]]--;
Vis[f[Lca][0]]--;
}
Dfs(Belong[1],0);
printf("%lld\n",Ans);
return 0;
}
```