树链剖分
对于2操作，记录一个delta数组就行了
对于1操作，将式子拆开：$w-dep[x]-dep[y]+2*dep[lca(x,y)]$，前面的都很好处理，主要是这个$lca$的部分，显然$lca$一定是$x$到$1$这条路径上的点，将这条路径上的权值加上$2$，那么对$y$的影响就是1到y这条路上的权值和了
AC代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
bool IOerror=0;
inline char nc() {
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend) {
p1=buf;
pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1) {
IOerror=1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
}
template<class T> inline bool read(T &x) {
bool sign=0;
char ch=nc();
x=0;
for(; blank(ch); ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
return true;
}
template<class T,class... U>bool read(T& h,U&... t) {
return read(h)&&read(t...);
}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 0x3f3f3f3f;
const int N = 5e4+10;
vector<int>e[N];
int dfn[N],top[N],siz[N],son[N],dep[N],fa[N],tim;
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
for(auto v:e[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;
dfn[u]=++tim;
if(!son[u]) return ;
dfs2(son[u],t);
for(auto v:e[u]){
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
struct node{
int l,r,mid,sum,lazy,len;
}tree[N<<2];
#define ls x<<1
#define rs x<<1|1
void pp(int x){
tree[x].sum=tree[ls].sum+tree[rs].sum;
}
void build(int x,int l,int r){
tree[x]={l,r,l+r>>1,0,0,r-l+1};
if(l==r) return ;
int mid=tree[x].mid;
build(ls,l,mid);
build(rs,mid+1,r);
}
void pd(int x){
if(tree[x].lazy){
int now=tree[x].lazy;
tree[ls].lazy+=now;
tree[rs].lazy+=now;
tree[ls].sum+=tree[ls].len*now;
tree[rs].sum+=tree[rs].len*now;
tree[x].lazy=0;
}
}
void modify(int x,int l,int r,int k){
if(l<=tree[x].l && tree[x].r<=r){
tree[x].lazy+=k;
tree[x].sum+=k*tree[x].len;
return ;
}
pd(x);
int mid=tree[x].mid;
if(l<=mid) modify(ls,l,r,k);
if(r>mid) modify(rs,l,r,k);
pp(x);
}
int query(int x,int l,int r){
if(l<=tree[x].l && tree[x].r<=r){
return tree[x].sum;
}
pd(x);
int ans=0;
int mid=tree[x].mid;
if(l<=mid) ans+=query(ls,l,r);
if(r>mid) ans+=query(rs,l,r);
return ans;
}
void change(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(1,dfn[top[x]],dfn[x],k);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
modify(1,dfn[x],dfn[y],k);
}
int Query(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(1,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(1,dfn[x],dfn[y]);
return ans;
}
int totadd,cnt,delta[N];
int getsum(int x){
return totadd-cnt*dep[x]+Query(1,x)-delta[x];
}
int n,m;
void init(){
totadd=0;
cnt=0;
tim=0;
for(int i=1;i<=n;i++){
e[i].clear();
delta[i]=0;
son[i]=0;
}
build(1,1,n);
}
int main() {
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int T;
read(T);
while(T--){
read(n,m);
init();
for(int i=1;i<n;i++){
int u,v;
read(u,v);
e[u].pb(v);
e[v].pb(u);
}
dfs1(1,0);
dfs2(1,1);
while(m--){
int op,x,w;
read(op,x);
if(op==1){
read(w);
totadd+=w-dep[x];
cnt++;
change(1,x,2);
}
if(op==2){
int now=getsum(x);
if(now>0) delta[x]+=now;
}
if(op==3){
printf("%d\n",getsum(x));
}
}
}
return 0;
}
动态点分治
对于2操作，记录一个delta数组就行了
对于1操作，建立点分树，维护权值和以及修改点数量，容斥计算答案
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
bool IOerror=0;
inline char nc() {
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if(p1==pend) {
p1=buf;
pend=buf+fread(buf,1,BUF_SIZE,stdin);
if(pend==p1) {
IOerror=1;
return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
}
template<class T> inline bool read(T &x) {
bool sign=0;
char ch=nc();
x=0;
for(; blank(ch); ch=nc());
if(IOerror)return false;
if(ch=='-')sign=1,ch=nc();
for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
if(sign)x=-x;
return true;
}
template<class T,class... U>bool read(T& h,U&... t) {
return read(h)&&read(t...);
}
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 5e4+10;
vector<int>e[N];
struct Grand_Father {
int deep[N], euler[N << 1], esiz, rid[N],log_2[N<<1];
void dfs(int u, int fa) {
deep[u] = deep[fa] + 1;
rid[u] = esiz + 1;
for(auto v:e[u]) {
if(v == fa) continue;
euler[++esiz] = u;
dfs(v, u);
}
euler[++esiz] = u;
}
int mn[N << 1][23];
inline void rmq_init() {
if(!log_2[2]) for(int i=2; i<N*2; i++) log_2[i] = log_2[i >> 1] + 1;
for(int i=1; i<=esiz; i++) mn[i][0] = euler[i];
for(int j=1; (1 << j) <= esiz; j++) {
for(int i=1; i + (1 << j) - 1 <= esiz; i++) {
if(deep[mn[i][j - 1]] < deep[mn[i + (1 << (j - 1))][j - 1]]) mn[i][j] = mn[i][j - 1];
else mn[i][j] = mn[i + (1 << (j - 1))][j - 1];
}
}
}
void solve(int s) {
esiz = 0;
dfs(s, 0);
rmq_init();
}
inline int rmq(int l, int r) {
int det = r - l + 1, kk = log_2[det];
if(deep[mn[l][kk]] <= deep[mn[r - (1 << kk) + 1][kk]]) return mn[l][kk];
else return mn[r - (1 << kk) + 1][kk];
}
inline int lca(int u, int v) {
int l = rid[u], r = rid[v];
if(l > r) swap(l, r);
return rmq(l, r);
}
inline int dis(int u, int v) {
return deep[u] + deep[v] - 2 * deep[lca(u,v)];
}
} LCA;
int dis(int x,int y) {
return LCA.dis(x,y);
}
int siz[N],tot,root,maxp[N],dfa[N];
bool vis[N];
void getroot(int u,int f) {
siz[u] = 1;
maxp[u] = 0;
for(auto v:e[u]) {
if(v==f || vis[v]) continue;
getroot(v,u);
siz[u]+=siz[v];
maxp[u] = max(maxp[u],siz[v]);
}
maxp[u] = max(maxp[u],tot-siz[u]);
if(maxp[u]<maxp[root]) root = u;
}
void div(int u) {
vis[u] = true;
int all = tot;
for(auto v:e[u]) {
if(vis[v]) continue;
tot=siz[v]>siz[u]? all - siz[u]:siz[v];
root=0;
maxp[root] = tot;
getroot(v,u);
dfa[root] = u;
div(root);
}
}
int s1[N],cnt1[N];
int s2[N],cnt2[N];
int delta[N];
void modify(int idx,int val) {
int now = idx;
while(now) {
int f = dfa[now];
s1[now] += val - dis(idx,now);
cnt1[now]++;
if(f) {
s2[now] += val - dis(idx,f);
cnt2[now]++;
}
now = f;
}
}
int query(int idx) {
int ans = -delta[idx];
int now = idx,last = 0;
while(now) {
ans+=s1[now];
if(last) {
ans -= s2[last];
ans -= (cnt1[now] - cnt2[last])*dis(now,idx);
}
last = now;
now = dfa[now];
}
return ans;
}
int n,m;
void init() {
LCA.solve(1);
root = 0;
tot = n;
maxp[root] = tot;
getroot(1,1);
div(root);
}
void prework() {
for(int i=1; i<=n; i++) {
e[i].clear();
delta[i] = 0;
dfa[i] = 0;
vis[i] = false;
s1[i] = cnt1[i] = 0;
s2[i] = cnt2[i] = 0;
}
for(int i=1; i<n; i++) {
int u,v;
read(u,v);
e[u].pb(v);
e[v].pb(u);
}
}
signed main() {
#ifdef xiaofan
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int T;
read(T);
while(T--) {
read(n,m);
prework();
init();
while(m--) {
int op,x,y;
read(op,x);
if(op == 1) {
read(y);
modify(x,y);
}
if(op == 2) {
int val = query(x);
if(val>0) delta[x]+=val;
}
if(op == 3) {
printf("%lld\n",query(x));
}
}
}
return 0;
}
