復(fù)雜度: O(nlog2n)
const int __=4e4+5;
struct edge{int x,v;}center;
bool del[__];//重心標(biāo)記
//以所在塊的重心x為根
//siz[y]: y子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
//d[y]: y距離x的距離
//TreeSize: 當(dāng)前樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
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;
}
復(fù)雜度: 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找重心并對(duì)邊權(quán)排序
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});
}
}
//找重心, 維護(hù)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)數(shù)量, 復(fù)雜度: 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;
}
復(fù)雜度: O(nlog2n+qlog2n)
const int __=1e5+5;
const int log2__=18;
struct edge{int x,v;}center;
//線(xiàn)性地址空間
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[]: 點(diǎn)分樹(shù)父節(jié)點(diǎn)
//f[x]: 點(diǎn)x作為重心的層數(shù)
//l[x]: 從x出發(fā)到子樹(shù)的最長(zhǎng)鏈長(zhǎng)度
int siz[__],v[__],pre[__],f[__],c[__],l[__];
//d[x][y]: 第x層點(diǎn)y距離重心的距離
//m[x][y]: 第x層點(diǎn)y映射到線(xiàn)性地址空間的位置
int d[log2__][__],m[log2__][__];
vector<int>G[__];
//p指向含根節(jié)點(diǎn)的樹(shù)狀數(shù)組首地址
//q指向不含根節(jié)點(diǎn)的樹(shù)狀數(shù)組首地址
int TreeSize,deep,*p,*q;
bool all=true;
void dfs(int x,int fa)
{
siz[x]=1;
d[deep][x]=l[x];
if(!all)
{
//插入樹(shù)狀數(shù)組中
add(p,l[x],v[x]);
add(q,l[x],v[x]);
//不包含根節(jié)點(diǎn)的各個(gè)子樹(shù)的起始位置
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;
//此時(shí)l[x]為: 點(diǎn)x的深度
l[y]=l[x]+1;
dfs(y,x);
maxs=max(maxs,siz[y]);
maxl=max(maxl,l[y]);
siz[x]+=siz[y];
}
//此時(shí)l[x]為: 從點(diǎn)x出發(fā)到子樹(shù)的最長(zhǎng)鏈長(zhǎng)度
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;
//維護(hù)整體信息
all=true;
//該dfs以重心為根
//處理出各個(gè)子樹(shù)的最長(zhǎng)鏈長(zhǎng)度l[y]與各個(gè)子樹(shù)的大小siz[y]
l[x]=0,dfs(x,-1);
o[++*o]=l[x];
//包含重心的所有子樹(shù)信息的樹(shù)狀數(shù)組的起始位置
m[dep][x]=*o;
p=o+*o;
*o+=l[x];
//維護(hù)子樹(shù)信息
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相鄰的點(diǎn)y為根
//處理出每個(gè)子樹(shù)的重心c[y], 并記錄點(diǎn)分樹(shù)父節(jié)點(diǎn)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;
}
