Tree
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1385 Accepted Submission(s): 237Problem DescriptionYou are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N
There are N – 1 edges numbered from 1 to N – 1.
Each node has a value and each edge has a value. The initial value is 0.
There are two kind of operation as follows:
● ADD1 u v k: for nodes on the path from u to v, the value of these nodes increase by k.
● ADD2 u v k: for edges on the path from u to v, the value of these edges increase by k.
After finished M operation on the tree, please output the value of each node and edge. InputThe first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each case contains two integers N ,M (1 ≤ N, M ≤105),denoting the number of nodes and operations, respectively.
The next N – 1 lines, each lines contains two integers u, v(1 ≤ u, v ≤ N ), denote there is an edge between u,v and its initial value is 0.
For the next M line, contain instructions “ADD1 u v k” or “ADD2 u v k”. (1 ≤ u, v ≤ N, -105 ≤ k ≤ 105) OutputFor each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.
The second line contains N integer which means the value of each node.
The third line contains N – 1 integer which means the value of each edge according to the input order. Sample Input
2
4 2
1 2
2 3
2 4
ADD1 1 4 1
ADD2 3 4 2
4 2
1 2
2 3
1 4
ADD1 1 4 5
ADD2 3 2 4
Sample Output
Case #1:
1 1 0 1
0 2 2
Case #2:
5 0 0 5
0 4 0题意：给出一棵树，树上的点和边的权值开始都是0，有两种操作，对于第一种操作，ADD1：在u到v的路径上每个点的权值+w；对于第二种操作ADD2：在u到v的路径上每个边的权值+w；最后询问每个点的权值和每条边的权值（按照输入的顺序）分析：首先两个dfs进行轻重链剖分，然后对于每个区间[L,R],在L的位置+w，在R+1的位置-w，保存在g1数组中，同理，对于边也一样，保存在g2数组里，最后从前往后做一遍扫描即可；程序：#pragma comment(linker, "/STACK:1024000000,1024000000")
#include"stdio.h"
#include"string.h"
#include"iostream"
#include"map"
#include"string"
#include"queue"
#include"stdlib.h"
#include"algorithm"
#include"math.h"
#define M 110009
#define eps 1e-5
#define inf 100000000
#define mod 100000000
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int v;
node(int vv){v=vv;}
};
vector<node>edge[M];
int pos,son[M],fa[M],p[M],fp[M],deep[M],top[M],num[M],g1[M],g2[M],ans[M];
void dfs(int u,int f,int d)
{
deep[u]=d;
fa[u]=f;
num[1]=1;
for(int i=0;i<(int)edge[u].size();i++)
{
int v=edge[u][i].v;
if(v==f)continue;
dfs(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[son[u]]<son[v])
son[u]=v;
}
}
void getpos(int u,int sp)
{
top[u]=sp;
p[u]=pos++;
fp[p[u]]=u;
if(son[u]==-1)return;
getpos(son[u],sp);
for(int i=0;i<(int)edge[u].size();i++)
{
int v=edge[u][i].v;
if(v==son[u]||v==fa[u])continue;
getpos(v,v);
}
}
void init()
{
pos=0;
memset(son,-1,sizeof(son));
dfs(1,1,1);
getpos(1,1);
}
void getnode(int u,int v,int d)
{
int f1=top[u];
int f2=top[v];
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
g1[p[f1]]+=d;
g1[p[u]+1]-=d;
u=fa[f1];
f1=top[u];
}
if(u==v)
{
g1[p[u]]+=d;
g1[p[u]+1]-=d;
return;
}
if(deep[u]>deep[v])swap(u,v);
g1[p[u]]+=d;
g1[p[v]+1]-=d;
return;
}
void getedge(int u,int v,int d)
{
int f1=top[u];
int f2=top[v];
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
g2[p[f1]]+=d;
g2[p[u]+1]-=d;
u=fa[f1];
f1=top[u];
}
if(u==v)
return;
if(deep[u]>deep[v])swap(u,v);
g2[p[son[u]]]+=d;
g2[p[v]+1]-=d;
return;
}
struct lede
{
int u,v;
}e[M];
int main()
{
int T,m,n,i,u,v,w,kk=1;
char ch[22];
cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<=n;i++)
edge[i].clear();
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
e[i].u=u;
e[i].v=v;
}
init();
memset(g1,0,sizeof(g1));
memset(g2,0,sizeof(g2));
while(m--)
{
scanf("%s%d%d%d",ch,&u,&v,&w);
if(strcmp(ch,"ADD1")==0)
getnode(u,v,w);
else
getedge(u,v,w);
}
printf("Case #%d:\n",kk++);
int sum=0;
for(i=0;i<pos;i++)
{
sum+=g1[i];
ans[i]=sum;
}
for(i=1;i<=n;i++)
{
if(i==1)
printf("%d",ans[p[i]]);
else
printf(" %d",ans[p[i]]);
}
printf("\n");
sum=0;
for(i=1;i<pos;i++)
{
sum+=g2[i];
ans[i]=sum;
}
for(i=1;i<n;i++)
{
if(deep[e[i].u]<deep[e[i].v])
swap(e[i].u,e[i].v);
if(i==1)
printf("%d",ans[p[e[i].u]]);
else
printf(" %d",ans[p[e[i].u]]);
}
printf("\n");
}
}
