生活随笔
收集整理的這篇文章主要介紹了
HDU 3966 Aragorns Story
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目
模板
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std
;
const int inf
=0x3f3f3f3f;
const int maxn
=2e5+10;
struct node
{int t
,nxt
;
}edge
[maxn
];
int head
[maxn
],cnt
;
void init(int n
)
{cnt
=0;memset(head
,-1,sizeof head
);
}
void addedge(int u
,int v
)
{edge
[cnt
]=node
{v
,head
[u
]};head
[u
]=cnt
++;
}
int dep
[maxn
],dad
[maxn
],size
[maxn
],son
[maxn
];
int top
[maxn
],seg
[maxn
],id
[maxn
];
void dfs1(int u
,int pre
)
{size
[u
]=1;son
[u
]=-1;int masize
=0;for(int i
=head
[u
];i
!=-1;i
=edge
[i
].nxt
){int v
=edge
[i
].t
;if(v
==pre
)continue;dad
[v
]=u
;dep
[v
]=dep
[u
]+1;dfs1(v
,u
);size
[u
]+=size
[v
];if(masize
<size
[v
]){masize
=size
[v
];son
[u
]=v
; }}
}
void dfs2(int u
,int fat
,int &tag
)
{top
[u
]=fat
;seg
[u
]=++tag
;id
[tag
]=u
;if(son
[u
]==-1)return;dfs2(son
[u
],fat
,tag
);for(int i
=head
[u
];i
!=-1;i
=edge
[i
].nxt
){int v
=edge
[i
].t
;if(v
==dad
[u
]||v
==son
[u
])continue;dfs2(v
,v
,tag
);}
}
void cuttree(int root
)
{int tag
=0;dep
[root
]=0;dad
[root
]=root
;dfs1(root
,root
);dfs2(root
,root
,tag
);
}
typedef long long ll
;
ll bit
[maxn
];
void add(int k
,ll num
,int limit
)
{for(;k
<=limit
;k
+=k
&(-k
))bit
[k
]+=num
;
}
ll
read(int k
)
{ll res
=0;for(;k
;k
-=k
&(-k
))res
+=bit
[k
];return res
;
}
void update(int left
,int right
,ll num
,int limit
)
{add(left
,num
,limit
);add(right
+1,-num
,limit
);
}
void modify(int u
,int v
,ll num
,int limit
)
{int fu
=top
[u
],fv
=top
[v
];while(fu
!=fv
){if(dep
[fu
]>=dep
[fv
]){update(seg
[fu
],seg
[u
],num
,limit
);u
=dad
[fu
],fu
=top
[u
];}else{update(seg
[fv
],seg
[v
],num
,limit
);v
=dad
[fv
],fv
=top
[v
];}}if(dep
[u
]>dep
[v
])swap(u
,v
);update(seg
[u
],seg
[v
],num
,limit
);
}
int a
[maxn
];
bool solve()
{int n
,m
,p
,u
,v
,k
;if(scanf("%d%d%d",&n
,&m
,&p
)==EOF)return 0;init(n
);for(int i
=1;i
<=n
;i
++)scanf("%d",&a
[i
]);for(int i
=1;i
<n
;i
++){scanf("%d%d",&u
,&v
);addedge(u
,v
);addedge(v
,u
);}cuttree(1);memset(bit
,0,sizeof bit
);for(int i
=1;i
<=n
;i
++)update(seg
[i
],seg
[i
],a
[i
],n
);char op
[3];while(p
--){scanf("%s",op
);if(op
[0]=='Q'){scanf("%d",&u
);ll ans
=read(seg
[u
]);printf("%lld\n",ans
);}else{scanf("%d%d%d",&u
,&v
,&k
);if(op
[0]=='D')k
=-k
;modify(u
,v
,k
,n
);}}return 1;}
int main()
{while(solve());}
總結(jié)
以上是生活随笔為你收集整理的HDU 3966 Aragorns Story的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
