bzoj3589 动态树
链接
思路
求链并。
发现只有最多5条链子，可以容斥。
链交求法：链顶是两条链顶深度大的那个，链底是两个链底的(lca)
如果链底深度小于链顶，就说明两条链没有交集。
复杂度(m*2^klog^2n)
还有一种做法。
把所有链子都打上(0/1tag)，只有(1)才能有贡献。
应该挺麻烦的，或者说都挺好写的。
代码
#include <bits/stdc++.h>
using namespace std;
const int _=4e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,Q,S[6],T[6];
struct node {int v,nxt;}e[_<<1];
int head[_],tot;
void add(int u,int v) {
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
namespace seg {
#define ls rt<<1
#define rs rt<<1|1
struct node {int l,r,siz,tot,lazy;}e[_<<2];
void build(int l,int r,int rt) {
e[rt].l=l,e[rt].r=r,e[rt].siz=r-l+1;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
}
void pushdown(int rt) {
if(e[rt].lazy) {
e[ls].tot+=e[ls].siz*e[rt].lazy;
e[rs].tot+=e[rs].siz*e[rt].lazy;
e[ls].lazy+=e[rt].lazy;
e[rs].lazy+=e[rt].lazy;
e[rt].lazy=0;
}
}
void modify(int L,int R,int ad,int rt) {
if(L<=e[rt].l&&e[rt].r<=R) {
e[rt].tot+=e[rt].siz*ad;
e[rt].lazy+=ad;
return;
}
int mid=(e[rt].l+e[rt].r)>>1;
pushdown(rt);
if(L<=mid) modify(L,R,ad,ls);
if(R>mid) modify(L,R,ad,rs);
e[rt].tot=e[ls].tot+e[rs].tot;
}
int query(int L,int R,int rt) {
if(L<=e[rt].l&&e[rt].r<=R) return e[rt].tot;
int mid=(e[rt].l+e[rt].r)>>1,ans=0;
pushdown(rt);
if(L<=mid) ans+=query(L,R,ls);
if(R>mid) ans+=query(L,R,rs);
return ans;
}
}
int dep[_],f[_],siz[_],son[_],top[_],idx[_],cnt;
void dfs1(int u,int fa) {
dep[u]=dep[fa]+1;
siz[u]=1;
f[u]=fa;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf) {
idx[u]=++cnt;
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(!idx[v]) dfs2(v,v);
}
}
int LCA(int x,int y) {
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=f[top[x]];
} if(dep[x]>dep[y]) swap(x,y);
return x;
}
int QQ(int x,int y) {
int tot=0;
while(top[x]!=top[y]) {
if(dep[top[x]]<dep[top[y]]) swap(x,y);
tot+=seg::query(idx[top[x]],idx[x],1);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
tot+=seg::query(idx[x],idx[y],1);
return tot;
}
void dsrrr(int &a,int &b,int x,int y) {
a=dep[a]>dep[x]?a:x,b=LCA(b,y);
if(dep[b]<dep[a]) a=-1,b=-1;
}
int calc(int x) {
int s=0,t=0;
for(int i=1;x;i++,x>>=1) {
if(x&1) {
if(!s&&!t) s=S[i],t=T[i];
else dsrrr(s,t,S[i],T[i]);
} if(s==-1&&t==-1) return 0;
}
return QQ(s,t);
}
int man[40];
int main() {
n=read();
for(int i=1,u,v;i<n;++i) {
u=read(),v=read();
add(u,v),add(v,u);
}
seg::build(1,n,1);
dfs1(1,0),dfs2(1,1);
Q=read();
for(int i=1;i<(1<<5);++i)
for(int j=0;j<5;++j)
if(i&(1<<j)) man[i]++;
while (Q --> 0) {
int opt=read();
if(!opt) {
int u=read(),val=read();
seg::modify(idx[u],idx[u]+siz[u]-1,val,1);
} else {
int k=read();
for(int i=1;i<=k;++i) {
S[i]=read(),T[i]=read();
if(dep[S[i]]>dep[T[i]]) swap(S[i],T[i]);
}
int ans=0;
for(int i=1;i<(1<<k);++i)
ans+=(man[i]&1?1:-1)*calc(i);
printf("%d
",ans&2147483647);
}
}
return 0;
}