问题描述
给定一棵有n个点的树(点的编号为1~n)，根为1，点有点权，设点i的初始值为0，给出q个操作，每个操作给出两个点和一个值，u,v,t，表示将u到v的路径上的所有点加t，输出所有操作后每个点的点权，。
输入格式
第一行输入两个整数n，q表示树的点的数目与操作次数
下面n-1行，每行两个整数x,y表示边的信息
下面q行，每行三个整数u,v,t表示将u到v的路径上的所有点加t
输出格式
n行，每行表示点i的权值
样例
in
5 5
1 2
1 3
2 4
2 5
1 5 1
2 5 10
3 4 3
2 4 4
1 2 4
out
8
22
3
7
11
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node{
int to;
int nxt;
}E[maxn<<1];
int h[maxn],w[maxn],dep[maxn],f[maxn][25],lg[maxn],etot;
void addedge(int x,int y)
{
E[++etot].to=y;
E[etot].nxt=h[x];
h[x]=etot;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
for (int i=1;(1<<i)<=dep[u];i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for (int i=h[u];i;i=E[i].nxt)
{
int v=E[i].to;
if (v!=fa)
{
dfs(v,u);
}
}
}
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
int d=dep[x]-dep[y];
while(d)
{
int k=lg[d];
x=f[x][k];
d=d-(1<<k);
}
if (x==y) return x;
for (int i=lg[dep[x]];i>=0;i--)
{
if (f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void dfs1(int u,int f)
{
for (int i=h[u];i;i=E[i].nxt)
{
int v;
v=E[i].to;
if (v!=f)
{
dfs1(v,u);
w[u]+=w[v];
}
}
}
int main()
{
int n,q;
cin>>n>>q;
for (int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
addedge(x,y);
addedge(y,x);
}
dfs(1,0);
for (int i=1;i<=q;i++)
{
int x,y,t;
cin>>x>>y>>t;
int l=lca(x,y);
w[x]+=t;
w[y]+=t;
w[l]-=t;
w[f[l][0]]-=t;
}
dfs1(1,0);
for (int i=1;i<=n;i++)
{
cout<<w[i]<<endl;
}
}
标签：每行,int,点权,dfs1,maxn,addedge From： https://www.cnblogs.com/smghj/p/16867143.html