复杂度: O(nlog²n)
const int __=4e4+5;
struct edge{int x,v;}center;
bool del[__];//重心标记
//以所在块的重心x为根
//siz[y]: y子树的节点个数
//d[y]: y距离x的距离
//TreeSize: 当前树的节点个数
int siz[__],d[__],TreeSize,k,ans;
vector<edge>G[__];
//找重心
void dfs(int x,int fa,int dis)
{
int maxx=0;
d[++*d]=dis,siz[x]=1;
for(edge &y:G[x])
{
int z=y.x;
if(z==fa || del[z])continue;
dfs(z,x,dis+y.v);
maxx=max(maxx,siz[z]);
siz[x]+=siz[z];
}
maxx=max(maxx,TreeSize-siz[x]);
if(maxx<center.v)center={x,maxx};
}
int cal(int a[],int n)
{
sort(a+1,a+1+n);
int res=0;
for(int l=1,r=n;l<r;++l)
{
for(;l<r && a[l]+a[r]>k;--r);
if(l!=r)res+=r-l;
}
return res;
}
void DivideConquer(int x)
{
*d=0,dfs(x,-1,0);
ans+=cal(d,*d);
del[x]=true;
for(edge &y:G[x])
{
if(del[y.x])continue;
center={0,TreeSize=siz[y.x]};
*d=0,dfs(y.x,-1,y.v);
ans-=cal(d,*d);
DivideConquer(center.x);
}
}
int main()
{
for(int n;~scanf("%d%d",&n,&k) && (n || k);)
{
for(int i=1;i<n;++i)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
G[x].push_back({y,z});
G[y].push_back({x,z});
}
ans=0;
DivideConquer(1);
printf("%d\n",ans);
for(int i=1;i<=n;++i)
{
del[i]=false;
G[i].clear();
}
}
return 0;
}
复杂度: O(nlogn)
const int __=5e4+5;
struct edge{int x,v;}center;
bool del[__],vis[__];
int siz[__],d[__],p[__],pre[__],maxs[__];
int TreeSize,k;
ll ans;
vector<int>G[__];
queue<edge>Q;
//bfs找重心并对边权排序
void bfs(edge x,bool b)
{
*d=0,vis[x.x]=b;
for(Q.push(x);!Q.empty();)
{
x=Q.front();Q.pop();
++*d;
d[*d]=x.v,p[*d]=x.x;
siz[x.x]=1,maxs[x.x]=0;
for(int &y:G[x.x])
if(vis[y]!=b && !del[y])
{
vis[y]=b;
pre[y]=x.x;
Q.push({y,x.v+1});
}
}
//找重心, 维护siz[]
for(int i=*d;i;--i)
{
int y=p[i],z=pre[y];
siz[z]+=siz[y];
maxs[z]=max(maxs[z],siz[y]);
maxs[y]=max(maxs[y],TreeSize-siz[y]);
if(maxs[y]<center.v)center={y,maxs[y]};
}
}
//找a[i]+a[j]==k && i<j的(i,j)数量, 复杂度: O(n)
ll cal(int a[],int n)
{
ll res=0;
int l=1,r=n,cnt=0;
for(;l<=n && a[l]+a[l]<k;++l)
{
for(;r && a[l]+a[r]>k;--r);
if(l==1 || a[l]!=a[l-1])cnt=0;
for(;r && a[l]+a[r]==k;--r)++cnt;
res+=cnt;
}
if(a[l]+a[r]==k)res+=1ll*(r-l+1)*(r-l)/2;
return res;
}
void DivideConquer(int x)
{
bfs({x,0},true);//vis[]=true;
ans+=cal(d,*d);
del[x]=true;
for(int &y:G[x])
{
if(del[y])continue;
center={0,TreeSize=siz[y]};
bfs({y,1},false);//vis[]=false;
ans-=cal(d,*d);
DivideConquer(center.x);
}
}
int main()
{
for(int n;~scanf("%d%d",&n,&k);)
{
for(int i=1;i<n;++i)
{
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
ans=0;
DivideConquer(1);
printf("%lld\n",ans);
for(int i=1;i<=n;++i)
{
del[i]=false;
G[i].clear();
}
}
return 0;
}
复杂度: O(nlog²n+qlog²n)
const int __=1e5+5;
const int log2__=18;
struct edge{int x,v;}center;
//线性地址空间
int o[3800190];
void add(int a[],int x,int v)
{
if(!x)return;
int n=*a;
for(;x<=n;x+=x&-x)
a[x]+=v;
}
int sum(int a[],int x)
{
int res=0;
for(x=min(*a,x);x;x-=x&-x)
res+=a[x];
return res;
}
//pre[]: 点分树父节点
//f[x]: 点x作为重心的层数
//l[x]: 从x出发到子树的最长链长度
int siz[__],v[__],pre[__],f[__],c[__],l[__];
//d[x][y]: 第x层点y距离重心的距离
//m[x][y]: 第x层点y映射到线性地址空间的位置
int d[log2__][__],m[log2__][__];
vector<int>G[__];
//p指向含根节点的树状数组首地址
//q指向不含根节点的树状数组首地址
int TreeSize,deep,*p,*q;
bool all=true;
void dfs(int x,int fa)
{
siz[x]=1;
d[deep][x]=l[x];
if(!all)
{
//插入树状数组中
add(p,l[x],v[x]);
add(q,l[x],v[x]);
//不包含根节点的各个子树的起始位置
m[deep][x]=*o;
}
int maxs=0,maxl=0;
for(int i=0;i<G[x].size();++i)
{
int y=G[x][i];
if(y==fa || f[y])continue;
//此时l[x]为: 点x的深度
l[y]=l[x]+1;
dfs(y,x);
maxs=max(maxs,siz[y]);
maxl=max(maxl,l[y]);
siz[x]+=siz[y];
}
//此时l[x]为: 从点x出发到子树的最长链长度
l[x]=max(l[x],maxl);
maxs=max(maxs,TreeSize-siz[x]);
if(maxs<center.v)center={x,maxs};
}
void DivideConquer(int x,int dep)
{
f[x]=deep=dep;
//维护整体信息
all=true;
//该dfs以重心为根
//处理出各个子树的最长链长度l[y]与各个子树的大小siz[y]
l[x]=0,dfs(x,-1);
o[++*o]=l[x];
//包含重心的所有子树信息的树状数组的起始位置
m[dep][x]=*o;
p=o+*o;
*o+=l[x];
//维护子树信息
all=false;
for(int i=0;i<G[x].size();++i)
{
int y=G[x][i];
if(f[y])continue;
TreeSize=siz[y];
center={0,TreeSize};
o[++*o]=l[y];
q=o+*o;
//该dfs以与重心x相邻的点y为根
//处理出每个子树的重心c[y], 并记录点分树父节点pre[c[y]]=x
l[y]=1,dfs(y,-1);
*o+=l[y];
c[y]=center.x;
pre[center.x]=x;
}
for(int i=0;i<G[x].size();++i)
{
int y=G[x][i];
if(f[y])continue;
TreeSize=siz[y];
DivideConquer(c[y],dep+1);
}
}
int query(int x,int k)
{
int res=v[x]+sum(o+m[f[x]][x],k);
for(int y=pre[x];y;y=pre[y])
{
int dep=f[y],dis=d[dep][x];
if(dis>k)continue;
res+=sum(o+m[dep][y],k-dis)+v[y]-sum(o+m[dep][x],k-dis);
}
return res;
}
void update(int x,int val)
{
for(int y=pre[x];y;y=pre[y])
{
int dep=f[y],dis=d[dep][x];
add(o+m[dep][y],dis,val-v[x]);
add(o+m[dep][x],dis,val-v[x]);
}
v[x]=val;
}
int main()
{
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)
scanf("%d",&v[i]);
for(int i=1;i<n;++i)
{
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
TreeSize=n;
center={0,TreeSize};
dfs(1,-1);
DivideConquer(center.x,1);
int ans=0;
while(q--)
{
int op,x,y;scanf("%d%d%d",&op,&x,&y);
x^=ans,y^=ans;
if(op==0)printf("%d\n",ans=query(x,y));
if(op==1)update(x,y);
}
return 0;
}
网友评论