| WZJ的数据结构（负三十） |
| 难度级别：D； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
给你一棵N个点的无根树，点和边上均有权值。请你设计一个数据结构，回答M次操作。 1 x v：对于树上的每一个节点y，如果将x、y在树上的距离记为d，那么将y节点的权值加上d*v。 2 x：询问节点x的权值。 |
|
输入
|
|
第一行为一个正整数N。
第二行到第N行每行三个正整数ui,vi,wi。表示一条树边从ui到vi，距离为wi。 第N+1行为一个正整数M。 最后M行每行三个或两个正整数，格式见题面。 |
|
输出
|
|
对于每个询问操作，输出答案。
|
|
输入示例
|
|
10
1 2 2 1 3 1 1 4 3 1 5 2 4 6 2 4 7 1 6 8 1 7 9 2 7 10 1 9 1 3 1 1 10 1 2 1 2 4 2 5 1 5 1 1 8 1 2 2 2 9 |
|
输出示例
|
|
6
6 10 22 24 |
|
其他说明
|
|
对于30%的数据：1<=N,M<=1000
另有50%的数据：1<=N,M<=100000，保证修改操作均在询问操作之前。 对于100%的数据：1<=N,M<=100000，1<=x<=N，1<=v,wi<=1000 |
题解：先想用点分治弄离线分数：首先转化问题，转换查询和修改的对象；然后窝萌变形一下查询所求，dist(x,y)*A[x]=(dep[x]+dep[y])*A[x]=dep[x]*A[x]+dep[y]*A[x];然后窝萌就是要求出dep[x]*A[x]和A[x]，这个扫两遍就好了。。。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
int n,Q,A[maxn],CG,f[maxn],siz[maxn],size;bool vis[maxn];
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
return;
}
long long ans[maxn],sum,sumd,tsum,tsumd;
void findcg(int x,int fa){
siz[x]=;int mxs=;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
findcg(v,x);siz[x]+=siz[v];mxs=max(mxs,siz[v]);
}
}f[x]=max(mxs,size-siz[x]);if(f[x]<f[CG])CG=x;return;
}
void dfs(int x,int fa,int dis){
//printf("(%d,%d) ",x,dis);
siz[x]=;tsum+=A[x]*dis;tsumd+=A[x];ans[x]+=dis*sumd+sum;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
dfs(v,x,dis+e->w);siz[x]+=siz[v];
}
}return;
}
void solve(int x=CG){
//printf("--------%d---------\n",x);
vis[x]=true;sum=;sumd=A[x];static ted*s[maxm];int top=;
for(ted*e=fch[x];e;e=e->nxt){
s[top++]=e;int v=e->y;
if(!vis[v])tsum=tsumd=,dfs(v,x,e->w),sum+=tsum,sumd+=tsumd;
//puts("");
}ans[x]+=sum;sum=;sumd=;
while(top--){
ted*e=s[top];int v=e->y;if(!vis[v])tsum=tsumd=,dfs(v,x,e->w),sum+=tsum,sumd+=tsumd;//puts("");
}
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
f[CG=]=size=siz[v];findcg(v,x);solve();
}
}return;
}
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
void init(){
n=read();int x,y;
for(int i=;i<n;i++)x=read(),y=read(),add(x,y,read());
return;
}
int Qs[maxn],M;
void work(){
Q=read();int tp,x;
while(Q--){
tp=read();x=read();
if(tp==)A[x]+=read();
else Qs[++M]=x;
}
f[CG=]=size=n;findcg(,);solve();
for(int i=;i<=M;i++)printf("%lld\n",ans[Qs[i]]);
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
/*
10
1 2 2
1 3 1
1 4 3
1 5 2
4 6 2
4 7 1
6 8 1
7 9 2
7 10 1
6
1 3 1
1 10 1
1 5 1
1 8 1
2 2
2 9
*/
动态树做法：%%%小健健，动态树分治其实就是把重心累成一棵树，这棵树保证了树高logn。窝萌把信息分三份累加在覆盖这个操作点的最多logn个重心上，分别是整棵子树的信息all，本子树到重心的父亲的距离信息cha &#%&！。。。（意会意会。。。），本子树到重心的距离信息tre @*%&#￥%……。。。（意会意会。。。）
有几个tips!
1.窝萌的一切操作都是在重心树上进行的！
2.tre,cha,all这些变量名称好眼熟？（。。。AAA树！。。。逃。。。
3.相当好写！压倒性优势胜过点分治有木有！
4.为了保持复杂度，询问两点距离这里采用了LCA转RMQ，做到了O(nlogn)-O(1)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct ted{int x,y,w;ted*nxt;}adj[maxm],*fch[maxn],*ms=adj;
void add(int x,int y,int w){
*ms=(ted){x,y,w,fch[x]};fch[x]=ms++;
*ms=(ted){y,x,w,fch[y]};fch[y]=ms++;
return;
}
int siz[maxn],CG,size,f[maxn],dep[maxn],mi[maxm][],Log[maxm],cnt,pos[maxn],fa[maxn];
bool vis[maxn];long long all[maxn],cha[maxn],tre[maxn];
void dfs(int x,int fa){
mi[++cnt][]=dep[x];pos[x]=cnt;siz[x]=;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
dep[v]=dep[x]+e->w;dfs(v,x);siz[x]+=siz[v];mi[++cnt][]=dep[x];
}
}return;
}
void initrmq(){
Log[]=-;for(int i=;i<=cnt;i++)Log[i]=Log[i>>]+;
for(int j=;(<<j)<=cnt;j++)
for(int i=;i+(<<j)-<=cnt;i++)
mi[i][j]=min(mi[i][j-],mi[i+(<<j-)][j-]);return;
}
int dist(int x,int y){
int ans=dep[x]+dep[y];x=pos[x];y=pos[y];if(x>y)swap(x,y);
int k=Log[y-x+];return ans-*min(mi[x][k],mi[y-(<<k)+][k]);
}
void findcg(int x,int fa){
siz[x]=;int mxs=;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(v!=fa&&!vis[v]){
findcg(v,x);siz[x]+=siz[v];mxs=max(siz[v],mxs);
}
}f[x]=max(mxs,size-siz[x]);if(f[x]<f[CG])CG=x;return;
}
void solve(int x=CG){
vis[x]=true;
for(ted*e=fch[x];e;e=e->nxt){
int v=e->y;if(!vis[v]){
f[CG=]=size=siz[v];findcg(v,x);fa[CG]=x;solve();
}
}return;
}
void update(int x,int v){
all[x]+=v;
for(int ret=x;fa[x];x=fa[x]){
long long d=dist(ret,fa[x]);
all[fa[x]]+=v;tre[fa[x]]+=d*v;cha[x]+=d*v;
}return;
}
long long query(int x){
long long ans=tre[x];
for(int ret=x;fa[x];x=fa[x]){
long long d=dist(ret,fa[x]);
ans+=tre[fa[x]]-cha[x]+(all[fa[x]]-all[x])*d;
}return ans;
}
inline int read(){
int x=,sig=;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=;
for(;isdigit(ch);ch=getchar())x=*x+ch-'';
return sig?x:-x;
}
inline void write(long long x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=;long long buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
int n,Q;
void init(){
n=read();int x,y;
for(int i=;i<n;i++)x=read(),y=read(),add(x,y,read());dfs(,);initrmq();
f[CG=]=size=n;findcg(,);solve();
Q=read();
while(Q--){
if(read()==)write(query(read())),ENT;
else x=read(),update(x,read());
}
return;
}
void work(){
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}
/*
7
1 5 4
1 2 5
1 3 1
3 6 2
3 4 6
4 7 2
1 6
*/