HDU - 4858
제목 링크: HDU - 4858
가장자리가 적기 때문에, 우리는 비수변을 단독으로 판단할 수 있다.
그리고 각 점이 인접한 점은 사실 BFS 시퀀스입니다.마지막으로 비수변을 단독으로 구해 보세요.
AC 코드:
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
const int N=1e5+10;
int n,st[N],ed[N],dfn[N],m,f[N],cnt,w[N],sum[N<<2],fa[N];
vector<int> g[N],v[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void bfs(){
queue<int> q; q.push(1); cnt=0; dfn[1]=++cnt;
while(q.size()){
int u=q.front(); q.pop();
for(int to:g[u]) if(!dfn[to]){
dfn[to]=++cnt; fa[to]=u;
if(!st[u]) st[u]=dfn[to];
ed[u]=max(ed[u],dfn[to]);
q.push(to);
}
}
}
#define mid (l+r>>1)
void change(int p,int l,int r,int x,int v){
if(l==r){sum[p]+=v; return ;}
if(x<=mid) change(p<<1,l,mid,x,v);
else change(p<<1|1,mid+1,r,x,v);
sum[p]=sum[p<<1]+sum[p<<1|1];
}
int ask(int p,int l,int r,int ql,int qr){
if(l==ql&&r==qr) return sum[p];
if(qr<=mid) return ask(p<<1,l,mid,ql,qr);
else if(ql>mid) return ask(p<<1|1,mid+1,r,ql,qr);
else return ask(p<<1,l,mid,ql,mid)+ask(p<<1|1,mid+1,r,mid+1,qr);
}
int calc(int x){
int res=w[fa[x]];
if(st[x]) res+=ask(1,1,n,st[x],ed[x]);
for(int to:v[x]) res+=w[to];
return res;
}
void solve(){
cin>>n>>m; memset(sum,0,sizeof sum);
assert(m>=n-1);
for(int i=1;i<=n;i++)
g[i].clear(),v[i].clear(),f[i]=i,st[i]=ed[i]=dfn[i]=w[i]=fa[i]=0;
for(int i=1,a,b;i<=m;i++){
scanf("%d %d",&a,&b);
int x=find(a),y=find(b);
if(x!=y) g[a].push_back(b),g[b].push_back(a),f[x]=y;
else v[a].push_back(b),v[b].push_back(a);
}
bfs(); int q; cin>>q;
for(int i=1,op,x,y;i<=q;i++){
scanf("%d %d",&op,&x);
if(!op) scanf("%d",&y),w[x]+=y,change(1,1,n,dfn[x],y);
else printf("%d
",calc(x));
}
}
signed main(){
int T; cin>>T; while(T--) solve();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.