POJ2763 Housewife Wind(DFS序)

题目:单边修改,树链查询。

这题是边权,不是点权,不过也可以看作是点权。

然后其实就和BZOJ2819一样。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111111
struct Edge{
int u,v,w,nxt;
}edge[MAXN<<];
int n,head[MAXN],NE;
void addEdge(int u,int v,int w){
edge[NE].u=u; edge[NE].v=v; edge[NE].w=w; edge[NE].nxt=head[u]; head[u]=NE++;
}
int odr,l[MAXN],r[MAXN],stack[MAXN],sum[MAXN],fa[][MAXN],dep[MAXN];
void dfs(){
int top=;
stack[++top]=;
while(top){
int u=stack[top];
if(l[u]){
r[u]=odr; --top;
continue;
}
l[u]=++odr;
for(int i=head[u]; i!=-; i=edge[i].nxt){
int v=edge[i].v;
if(fa[][u]==v) continue;
fa[][v]=u; dep[v]=dep[u]+; sum[v]=sum[u]+edge[i].w;
stack[++top]=v;
}
}
} int N,tree[MAXN<<],x,y,z;
void update(int i,int j,int k){
if(x<=i && j<=y){
tree[k]+=z;
return;
}
if(tree[k]){
tree[k<<]+=tree[k]; tree[k<<|]+=tree[k];
tree[k]=;
}
int mid=i+j>>;
if(x<=mid) update(i,mid,k<<);
if(y>mid) update(mid+,j,k<<|);
}
int query(int i,int j,int k){
if(i==j) return tree[k];
if(tree[k]){
tree[k<<]+=tree[k]; tree[k<<|]+=tree[k];
tree[k]=;
}
int mid=i+j>>;
if(x<=mid) return query(i,mid,k<<);
return query(mid+,j,k<<|);
}
int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int k=; k<; ++k){
if((dep[v]-dep[u])>>k&){
v=fa[k][v];
}
}
if(v==u) return u;
for(int k=; k>=; --k){
if(fa[k][u]!=fa[k][v]){
u=fa[k][u];
v=fa[k][v];
}
}
return fa[][u];
}
void init(){
dfs();
for(int i=; i<; ++i){
for(int j=; j<=n; ++j){
int t=fa[i-][j];
fa[i][j]=fa[i-][t];
}
}
for(N=; N<odr; N<<=);
for(int i=; i<=n; ++i){
x=l[i]; y=l[i]; z=sum[i];
update(,N,);
}
} int main(){
int q,s,op,a,b,c;
memset(head,-,sizeof(head));
scanf("%d%d%d",&n,&q,&s);
for(int i=; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
init();
while(q--){
scanf("%d",&c);
if(c){
scanf("%d%d",&a,&b);
Edge &e=edge[a-<<];
if(fa[][e.u]==e.v){
x=l[e.u]; y=r[e.u]; z=b-e.w;
}else{
x=l[e.v]; y=r[e.v]; z=b-e.w;
}
e.w=b;
update(,N,);
}else{
scanf("%d",&a);
int res;
x=l[a]; res=query(,N,);
x=l[s]; res+=query(,N,);
x=l[lca(a,s)]; res-=(query(,N,)<<);
s=a;
printf("%d\n",res);
}
}
return ;
}
上一篇:Linux 终端访问 FTP 及 上传下载 文件[转]


下一篇:linux终端terminal个性化配置(转)