| 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 |
将问题转化为计算贡献，那么修改对应更改点权，查询对应带权距离之和，动态树分治就可以了。
用sz表示子树中权值之和，sumv表示子树所有点到其带权距离之和，sumv2表示子树所有点到其父亲带权距离之和。
两个操作均是O(logn)
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int n,q,first[maxn],next[maxn<<],to[maxn<<],dis[maxn<<],e;
void AddEdge(int w,int v,int u) {
to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;
to[++e]=u;dis[e]=w;next[e]=first[v];first[v]=e;
}
int mn[maxn<<][],Log[maxn<<],dep[maxn],pos[maxn],cnt;
void dfs(int x,int fa) {
mn[++cnt][]=dep[x];pos[x]=cnt;
ren if(to[i]!=fa) dep[to[i]]=dep[x]+dis[i],dfs(to[i],x),mn[++cnt][]=dep[x];
}
void pre() {
Log[]=-;
rep(i,,cnt) Log[i]=Log[i>>]+;
for(int j=;(<<j)<=cnt;j++)
for(int i=;i+(<<j)-<=cnt;i++)
mn[i][j]=min(mn[i][j-],mn[i+(<<j-)][j-]);
}
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(mn[x][k],mn[y-(<<k)+][k]);
}
int vis[maxn],f[maxn],s[maxn],size,root;
void getroot(int x,int fa) {
s[x]=;int maxs=;
ren if(to[i]!=fa&&!vis[to[i]]) {
getroot(to[i],x);
s[x]+=s[to[i]];
maxs=max(maxs,s[to[i]]);
}
f[x]=max(size-s[x],maxs);
if(f[x]<f[root]) root=x;
}
int fa[maxn];
void solve(int x) {
vis[x]=;
ren if(!vis[to[i]]) {
size=f[]=s[to[i]];getroot(to[i],root=);
fa[root]=x;solve(root);
}
}
ll sz[maxn],sumv[maxn],sumv2[maxn];
void update(int v,int x) {
sz[x]+=v;
for(int i=x;fa[i];i=fa[i]) {
int D=dist(x,fa[i]);
sz[fa[i]]+=v;sumv[fa[i]]+=(ll)D*v;sumv2[i]+=(ll)D*v;
}
}
ll query(int x) {
ll ans=sumv[x];
for(int i=x;fa[i];i=fa[i]) {
int D=dist(x,fa[i]);
ans+=(sumv[fa[i]]-sumv2[i])+(sz[fa[i]]-sz[i])*D;
}
return ans;
}
int main() {
n=read();
rep(i,,n) AddEdge(read(),read(),read());
dfs(,);pre();
size=f[]=n;getroot(,);solve(root);
q=read();
while(q--)
if(read()==) printf("%lld\n",query(read()));
else update(read(),read());
return ;
}