HDU5039 水题当成神题做了。 明显这题直接用线段树去搞就可以的。 但是比赛时候想出来的用树链剖分的写法，把代码修正下就过了。 关于做法，可以参考QTREE4的树链剖分做法。 可以看漆子超论文 里面关于QTREE4的树链剖分做法还是比较详细的。 其实就是把树分成一条一条链。 然后每条链使用线段树去维护，因为需要修改单点，查询。 修改的时候，最多变化logn条链。 这题的话， 维护单挑链的值，一个是 l0表示到左端点经过偶数条1边的点数，l1表示左端点经过奇数条1边的点数。 r0,r1类似。 然后sum是需要求的点数。 这种做法虽然比较烦，但是思想还是很好的。

# Hilarity

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 165 Accepted Submission(s): 32

Problem Description

Input

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow. For each test case, the first line contains N (1<=N<=30000) describing the number of cities. Then N lines follow. The ith line of these contains the name of the ith city, it’s a string containing only letters and will not be longer than 10. The following N - 1 lines indicate the N - 1 edges between cities. Each of these lines will contain two strings for the cities’ name and a integer for the initial status of the edge (0 for empty, 1 for crowded). Then an integer M (1<=M<=60000) describes the number of queries. There are two kinds of query: ● “M i” means the status changing of the ith (starting from 1) road (0 to 1, 1 to 0); ● “Q” means that Matt asks you the number of different paths.

Output

For each test case, first output one line “Case #x:”, where x is the case number (starting from 1). Then for each “Q” in input, output a line with the answer.

Sample Input

1 5 a b c d e a b 1 b c 0 c d 1 d e 1 7 Q M 1 Q M 3 Q M 4 Q

Sample Output

Case #1: 12 8 8 0

Source

2014 ACM/ICPC Asia Regional Beijing Online

#include <stdio.h>

#include

#include

#include

#include

#include <string.h>

#include

#include

#include

#include <math.h>
using namespace std;
const int MAXN = 30010;
const int INF = 0x3f3f3f3f;
struct Edge{
int to,next;
int f;
}edge[MAXN2];
void init(){
tot = 0;
}
edge[tot].to = v;
edge[tot].f = f;
}
long long ans;
int num0[MAXN],num1[MAXN];
long long tnum[MAXN];
struct Node{
int l0,l1;
int r0,r1;
int cc;
long long sum;
Node gao(int u){
l0 = r0 = num0[u];
l1 = r1 = num1[u];
sum = tnum[u];
cc = 0;
return
this;
}
};
int pos[MAXN];
int val[MAXN];
int fa[MAXN];
int cnt[MAXN];
int col[MAXN];
int CHANGEU;
struct chain{
vectoruu;
vectornde;
int n;
void init(){
n = uu.size();
nde.resize(n << 2);
for(int i = 0;i < n;i++)pos[uu[i]] = i;
build(0,n-1,1);
}
void up(int l,int r,int p){
int mid = (l+r)>>1;
nde[p].cc = nde[p<<1].cc ^ nde[(p<<1)|1].cc ^ val[uu[mid]];
nde[p].l0 = nde[p<<1].l0;
nde[p].l1 = nde[p<<1].l1;
if(nde[p<<1].cc^val[uu[mid]]){
nde[p].l0 += nde[(p<<1)|1].l1;
nde[p].l1 += nde[(p<<1)|1].l0;
}
else {
nde[p].l0 += nde[(p<<1)|1].l0;
nde[p].l1 += nde[(p<<1)|1].l1;
}
nde[p].r0 = nde[(p<<1)|1].r0;
nde[p].r1 = nde[(p<<1)|1].r1;
if(nde[(p<<1)|1].cc^val[uu[mid]]){
nde[p].r0 += nde[p<<1].r1;
nde[p].r1 += nde[p<<1].r0;
}
else {
nde[p].r0 += nde[p<<1].r0;
nde[p].r1 += nde[p<<1].r1;
}
if(val[uu[mid]] == 0){
nde[p].sum = nde[p<<1].sum + nde[(p<<1)|1].sum +
(long long)nde[p<<1].r0nde[(p<<1)|1].l1 +
(long long)nde[p<<1].r1
nde[(p<<1)|1].l0;
}
else {
nde[p].sum = nde[p<<1].sum + nde[(p<<1)|1].sum +
(long long)nde[p<<1].r0nde[(p<<1)|1].l0 +
(long long)nde[p<<1].r1
nde[(p<<1)|1].l1;
}
}
void build(int l,int r,int p){
if(l == r){
nde[p].gao(uu[l]);
return;
}
int mid = (l+r)/2;
build(l,mid,p<<1);
build(mid+1,r,(p<<1)|1);
up(l,r,p);
}
void update(int k,int l,int r,int p){
if(l == r){
nde[p].gao(uu[k]);
return;
}
int mid = (l+r)/2;
if(k <= mid)update(k,l,mid,p<<1);
else update(k,mid+1,r,(p<<1)|1);
up(l,r,p);
}
int change(int y){
int x = uu.back();
int p = fa[x];
if(p){
if(x == CHANGEU)val[x] ^= 1;
if(val[x]){
tnum[p] -= (long long)nde.r0(num0[p]-nde.r1);
tnum[p] -= (long long)nde.r1
(num1[p]-nde.r0);
num0[p] -= nde.r1;
num1[p] -= nde.r0;
}
else {
tnum[p] -= (long long)nde.r1(num0[p]-nde.r0);
tnum[p] -= (long long)nde.r0
(num1[p]-nde.r1);
num0[p] -= nde.r0;
num1[p] -= nde.r1;
}
if(x == CHANGEU)val[x] ^= 1;
}
ans -= nde.sum;
update(pos[y],0,n-1,1);
if(p){
if(val[x]){
tnum[p] += (long long)nde.r0num0[p];
tnum[p] += (long long)nde.r1
num1[p];
num0[p] += nde.r1;
num1[p] += nde.r0;
}
else {
tnum[p] += (long long)nde.r0num1[p];
tnum[p] += (long long)nde.r1
num0[p];
num0[p] += nde.r0;
num1[p] += nde.r1;
}
}
ans += nde.sum;
return p;
}
}ch[MAXN];
void dfs1(int u,int pre){
chain &c = ch[u];
c.uu.clear();
int v, x = 0;
cnt[u] = 1;
for(int i = head[u];i != -1;i = edge[i].next){
v = edge[i].to;
if(v == pre)continue;
dfs1(v,u);
val[v] = edge[i].f;
cnt[u] += cnt[v];
fa[v] = u;
if(cnt[v] > cnt[x]) x = v;
}
if(!x)col[u] = u;
else col[u] = col[x];
ch[col[u]].uu.push_back(u);
num0[u] = 1;
num1[u] = 0;
tnum[u] = 0;

}
void dfs2(int x){
x = col[x];
chain &c = ch[x];
int n = c.uu.size();
int u,v;
for(int i = 1;i < n;i++){
u = c.uu[i];
for(int j = head[u];j != -1;j = edge[j].next){
v = edge[j].to;
if(v == c.uu[i-1] || fa[u] == v)continue;
dfs2(v);
if(val[v]){
tnum[u] += (long long)num0[u]*ch[col[v]].nde.r0 + (long long)num1[u]*ch[col[v]].nde.r1;
num0[u] += ch[col[v]].nde.r1;
num1[u] += ch[col[v]].nde.r0;
}
else {
tnum[u] += (long long)num1[u]*ch[col[v]].nde.r0 + (long long)num0[u]*ch[col[v]].nde.r1;
num0[u] += ch[col[v]].nde.r0;
num1[u] += ch[col[v]].nde.r1;
}
}
}
c.init();
ans += c.nde.sum;
}
char str;
char str1,str2;
int main()
{
int T;
int iCase = 0;
scanf(“%d”,&T);
int n;
while(T–){
ans = 0;
iCase++;
scanf(“%d”,&n);
map<string,int>mp;
init();
for(int i = 1;i <= n;i++){
scanf(“%s”,str);
mp[str] = i;
}
int u,v,f;
for(int i = 1;i < n;i++){
scanf(“%s%s%d”,str1,str2,&f);
}
int Q;
char op;
scanf(“%d”,&Q);
printf(“Case #%d:\n”,iCase);
val = 0;
fa = 0;
dfs1(1,1);
dfs2(1);
while(Q–){
scanf(“%s”,op);
if(op == ‘Q’){
printf(“%I64d\n”,ans*2);
}
else {
int id ;
scanf(“%d”,&id);
id–;
val[u] ^= 1;
CHANGEU = u;
while(u)
u = ch[col[u]].change(u);
}
}
}
return 0;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 402.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%