树链剖分裸题。。。。
又要扩栈又要输入挂还卡格式。。。。真无语
Tree
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1538 Accepted Submission(s): 261
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.
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 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.
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
Case #1: 1 1 0 1 0 2 2 Case #2: 5 0 0 5 0 4 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int maxn=100100;
int nextInt()
{
char ch;
int ok=0,fu=0,ans=0;
while(ch=getchar())
{
if(ch=='-'||(ch>='0'&&ch<='9'))
{
ok=1;
if(ch=='-') fu=1;
else
{
ans=ans*10+(ch-'0');
}
}
else if(ok==1) break;
}
if(fu) ans=-ans;
return ans;
}
struct Edge
{
int to,next;
}edge[maxn*2];
int Adj[maxn],Size;
void add_edge(int u,int v)
{
edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++;
}
int fa[maxn],deep[maxn],num[maxn],son[maxn];
int top[maxn],p[maxn],rp[maxn],pos;
int tree[2][maxn],n,m;
inline int lowbit(int x)
{
return x&(-x);
}
void ADD(int id,int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
tree[id][i]+=v;
}
int SUM(int id,int p)
{
int ret=0;
for(int i=p;i;i-=lowbit(i))
ret+=tree[id][i];
return ret;
}
void init()
{
memset(Adj,-1,sizeof(Adj));
memset(son,-1,sizeof(son));
memset(tree,0,sizeof(tree));
Size=0;pos=1;
}
void dfs1(int u,int pre,int d)
{
num[u]=1; fa[u]=pre; deep[u]=d;
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre) continue;
dfs1(v,u,d+1);
num[u]+=num[v];
if(son[u]==-1||num[son[u]]<num[v])
{
son[u]=v;
}
}
}
void getP(int u,int tp)
{
top[u]=tp; p[u]=pos++; rp[p[u]]=u;
if(son[u]!=-1) getP(son[u],tp);
for(int i=Adj[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v!=fa[u]&&v!=son[u])
getP(v,v);
}
}
void Change(int u,int v,int k)
{
int f1=top[u],f2=top[v];
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(f1,f2); swap(u,v);
}
ADD(0,p[f1],k); ADD(0,p[u]+1,-k);
u=fa[f1]; f1=top[u];
}
if(deep[u]<deep[v]) swap(u,v);
ADD(0,p[v],k); ADD(0,p[u]+1,-k);
}
void Change2(int u,int v,int k)
{
int f1=top[u],f2=top[v];
while(f1!=f2)
{
if(deep[f1]<deep[f2])
{
swap(f1,f2); swap(u,v);
}
ADD(1,p[f1]-1,k); ADD(1,p[u],-k);
u=fa[f1]; f1=top[u];
}
if(u==v) return ;
if(deep[u]<deep[v]) swap(u,v);
ADD(1,p[son[v]]-1,k);
ADD(1,p[u],-k);
}
int bian[maxn][2];
int main()
{
int T_T,cas=1;
scanf("%d",&T_T);
while(T_T--)
{
init();
scanf("%d%d",&n,&m);
for(int i=0;i<n-1;i++)
{
int a,b;
a=nextInt(); b=nextInt();
add_edge(a,b);
add_edge(b,a);
bian[i][0]=a;bian[i][1]=b;
}
dfs1(1,0,0);
getP(1,1);
for(int i=0;i<n-1;i++)
{
if(deep[bian[i][0]]<deep[bian[i][1]])
swap(bian[i][0],bian[i][1]);
}
while(m--)
{
char op[10];
int a,b,c;
scanf("%s",op);
a=nextInt(); b=nextInt(); c=nextInt();
if(op[3]=='1')
{
Change(a,b,c);
}
else if(op[3]=='2')
{
Change2(a,b,c);
}
}
printf("Case #%d:\n",cas++);
for(int i=1;i<=n;i++)
printf("%d%c",SUM(0,p[i]),(i==n)?'\n':' ');
for(int i=0;i<n-1;i++)
{
printf("%d%c",SUM(1,p[bian[i][0]]-1),(i==n-2)?'\n':' ');
}
if(n==1) putchar(10);
}
return 0;
}