HDU 3966 Aragorn's Story [树链剖分(点权)+树状数组]【数据
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3966 ——————————————————————————-. Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Input For each case,The first line contains three integers N,M,P which means there will be N(1 ≤ N ≤ 50000) camps,M(M = N-1) edges and P(1 ≤ P ≤ 100000) operations. The number of camps starts from 1. The next line contains N integers A1,A2,…AN(0 ≤ Ai ≤ 1000),means at first in camp-i has Ai enemies. The next M lines contains two integers u and v for each,denotes that there is an edge connects camp-u and camp-v. The next P lines will start with a capital letter ‘I’,‘D’ or ‘Q’ for each line. ‘I’,followed by three integers C1,C2 and K( 0≤K≤1000),which means for camp C1,increase K soldiers to these camps. ‘D’,decrease K soldiers to these camps. ‘Q’,followed by one integer C,which is a query and means Aragorn wants to know the number of enemies in camp C at that time. Output Sample Input Sample Output 1.The number of enemies may be negative. 2.Huge input,be careful. ————————————————————————-. 题目大意: 解题思路: 但是这题简单在 只要用树状数组维护就行了, 坑比的我居然折在了输入上, 也后输入字符一论用
附本题代码 #include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int INF = (~(1<<31));
const int N = 50000+7;
const double eps = 1e-7;
inline int read(){
int x=0,f=1;char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
/****************************************************/
int w[N],n,m,q;
vector<int >G[N];
void add(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
int fa[N],dep[N],son[N],sz[N];
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,sz[u]=1;
int gz=G[u].size();
for(int to,i=0;i<gz;i++){
to=G[u][i];
if(to==f) continue;
dfs1(to,u,d+1);
sz[u]+=sz[to];
if(sz[son[u]]<sz[to])son[u]=to;
}
}
int top[N],tree[N],pre[N],cnt;
void dfs2(int u,int tp){
top[u]=tp,tree[u]=++cnt,pre[tree[u]]=u;
if(son[u]) dfs2(son[u],tp);
int gz=G[u].size();
for(int to,i=0;i<gz;i++){
to=G[u][i];
if(to==son[u]||to==fa[u])continue;
dfs2(to,to);
}
}
int sum[N];
#define lowbit(x) (x&-x)
void update(int index,int val){
for(int i=index;i<=n;i+=lowbit(i))sum[i]+=val;
}
int getSum(int index){
int ans = 0;
for(int i=index;i;i-=lowbit(i)) ans+=sum[i];
return ans;
}
int update(int x,int y,int k){
int fx=top[x],fy=top[y];
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
update(tree[fx],k),update(tree[x]+1,-k);
x=fa[fx],fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
update(tree[x],update(tree[y]+1,-k);
}
void init(){
cnt = 0;
for(int i=0;i<=n;i++)son[i]=0;
}
int main(){
while(~scanf("%d%d%d",&n,&m,&q)){
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
init();
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++)update(tree[i],w[i]),update(tree[i]+1,-w[i]);
char ch,s[10];
int a,b,k;
while(q--){
scanf("%s",s);
ch=s[0];
if(ch=='Q'){
scanf("%d",&a);
printf("%dn",getSum(tree[a]));
}
else {
scanf("%d%d%d",&a,&b,&k);
if(ch=='D') k=-k;
update(a,k);
}
}
for(int i=1;i<=n;i++)G[i].clear();
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |