HDU5044 2014上海市网络赛1003 tree
HDU5044 2014上海网络赛1003 tree
Total Submission(s): 1024 Accepted Submission(s): 188
转载挺注明出处:http://blog.csdn.net/hitwhacmer1
Tree
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Tree
Total Submission(s): 1024 Accepted Submission(s): 188
Problem Description
You 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.
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.
Input
The 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)
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)
Output
For 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.
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
//去年学长做的时候还能过,记得是G++跑过的,现在做就要c++然后手动开栈才跑了3000+ms,不知道是不是新加了数据。 #include<stdio.h> #include<string.h> #include<math.h> #include <string> #include<algorithm> #include<iostream> #include<queue> #include<stack> #include<vector> #include<list> #include<map> #include<set> #include<cmath> #define CL(x,v); memset(x,v,sizeof(x)); #define INF 1<<29 #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) #define EPS 1e-8 #define MID int mid=(l+r)>>1; int ls=o<<1; int rs=o<<1|1; #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int N=100005; int father[N]; bool vis[N]; int op[N]; int a[N],b[N],lca[N]; long long v[N]; long long dis[N]; long long dis2[N]; int faa[N]; int out[N]; struct Edge{ int v,next,id; }e[N*4]; int head[N],ask[N]; int cnt; void add1(int u,int v,int id) { e[cnt].v=v; e[cnt].next=head[u]; e[cnt].id=id; head[u]=cnt++; } void add2(int u,int v,int id) { e[cnt].v=v; e[cnt].next=ask[u]; e[cnt].id=id; ask[u]=cnt++; } int Find(int x) { if(father[x]==x)return x; return father[x]=Find(father[x]); } void LCA(int now,int fa) { faa[now]=fa; father[now]=now; vis[now]=true; for(int i=ask[now];i!=-1;i=e[i].next){ int v=e[i].v; int id=e[i].id; if(vis[v]) lca[id]=Find(v); } for(int i=head[now];i!=-1;i=e[i].next){ int v=e[i].v; int id=e[i].id; if(v==fa) continue; out[id]=v; LCA(v,now); father[v]=now; } } void dfs(int now,int fa) { long long ret=0; long long ret2=0; for(int i=head[now];i!=-1;i=e[i].next){ int v=e[i].v; if(v==fa)continue; dfs(v,now); ret+=dis[v]; ret2+=dis2[v]; } dis[now]+=ret; dis2[now]+=ret2; } int main() { int T; int n,m; int x,y; char str[5]; int Case=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); memset(dis2,0,sizeof(dis2)); memset(head,-1,sizeof(head)); memset(ask,-1,sizeof(ask)); cnt=0; for(int i=0;i<n-1;i++){ scanf("%d%d",&x,&y); add1(x,y,i); add1(y,x,i); } for(int i=0;i<m;i++){ scanf("%s%d%d%I64d",str,&x,&y,&v[i]); if(str[3]=='1')op[i]=1; else op[i]=2; a[i]=x;b[i]=y; add2(x,y,i); add2(y,x,i); } LCA(1,-1); faa[1]=0; for(int i=0;i<m;i++){ if(op[i]==2){ dis[a[i]]+=v[i]; dis[b[i]]+=v[i]; dis[lca[i]]-=v[i]*2; }else { dis2[a[i]]+=v[i]; dis2[b[i]]+=v[i]; dis2[lca[i]]-=v[i]; dis2[faa[lca[i]]]-=v[i]; } } dfs(1,-1); printf("Case #%d:\n",Case++); printf("%I64d",dis2[1]); for(int i=2;i<=n;i++){ printf(" %I64d",dis2[i]); }printf("\n"); if(n==1) {printf("\n");continue;} printf("%I64d",dis[out[0]]); for(int i=1;i<n-1;i++){ printf(" %I64d",dis[out[i]]); }printf("\n"); } return 0; }
其中对点值的更新,一次操作其中为什么最近公共祖先要减v,而它的父节点也要减v,从差分数列的角度考虑要想从a[i]到a[j]都加上d,那么b[i]+d,b[j+1]-d,那么从x到y要想更新值,那么就要将x到lca看成一个差分数列,把y到lca的父节点看陈给一个差分数列如图,那么x到lca之前的那个点要更新,就执行
- dis2[b[i]]+=v[i];
- dis2[lca[i]]-=v[i];如果y到lca想更新,那么就要y处加v,lca的爸爸减v,那么从x到y的路上的点全都更新了
- 边一个道理,但是边不会更新两次,就直接lca处减2*v就好了
版权声明:本文为博主原创文章,转载请注明出处http://blog.csdn.net/hitwhacmer1