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
After June 1st, elementary students of Ted Land are still celebrating “The Sacred Day of Elementary Students”. They go to the streets and do some elementary students stuff. So we call them “elementary students”. There are N cities in Ted Land. But for simplicity, the mayor Matt only built N - 1 roads so that all cities can reach each other. Some of the roads are occupied by the “elementary students”. They will put an celebration hat on everyone who goes through the road without one. But if someone goes through the road with a celebration hat on his head, “elementary students” will steal the hat for no reason. Since Matt doesn’t have a celebration hat, he wants to know how many different paths in his land that he can end up with a hat. Two paths are considered to be different if and only if they have different start city or end city. As the counsellor of the mayor Matt, you have to answer this question for him. The celebration elementary students are not stable: sometimes a new crowd of elementary students go to an empty road; sometimes the elementary students on a road will go back home and remain the road empty. Matt will send you the monitor about the change of elementary students on road and ask you the question above. You will be fired if you answer wrong.
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];
int head[MAXN],tot;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int f){
edge[tot].to = v;
edge[tot].next = head[u];
edge[tot].f = f;
head[u] = tot++;
}
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 link[MAXN];
int CHANGEU;
struct chain{
vector
vector
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].r1nde[(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].r1nde[(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[1].r0(num0[p]-nde[1].r1);
tnum[p] -= (long long)nde[1].r1(num1[p]-nde[1].r0);
num0[p] -= nde[1].r1;
num1[p] -= nde[1].r0;
}
else {
tnum[p] -= (long long)nde[1].r1(num0[p]-nde[1].r0);
tnum[p] -= (long long)nde[1].r0(num1[p]-nde[1].r1);
num0[p] -= nde[1].r0;
num1[p] -= nde[1].r1;
}
if(x == CHANGEU)val[x] ^= 1;
}
ans -= nde[1].sum;
update(pos[y],0,n-1,1);
if(p){
if(val[x]){
tnum[p] += (long long)nde[1].r0num0[p];
tnum[p] += (long long)nde[1].r1num1[p];
num0[p] += nde[1].r1;
num1[p] += nde[1].r0;
}
else {
tnum[p] += (long long)nde[1].r0num1[p];
tnum[p] += (long long)nde[1].r1num0[p];
num0[p] += nde[1].r0;
num1[p] += nde[1].r1;
}
}
ans += nde[1].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);
link[i/2] = v;
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[1].r0 + (long long)num1[u]*ch[col[v]].nde[1].r1;
num0[u] += ch[col[v]].nde[1].r1;
num1[u] += ch[col[v]].nde[1].r0;
}
else {
tnum[u] += (long long)num1[u]*ch[col[v]].nde[1].r0 + (long long)num0[u]*ch[col[v]].nde[1].r1;
num0[u] += ch[col[v]].nde[1].r0;
num1[u] += ch[col[v]].nde[1].r1;
}
}
}
c.init();
ans += c.nde[1].sum;
}
char str[100];
char str1[100],str2[100];
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);
addedge(mp[str1],mp[str2],f);
addedge(mp[str2],mp[str1],f);
}
int Q;
char op[10];
scanf(“%d”,&Q);
printf(“Case #%d:\n”,iCase);
val[1] = 0;
fa[1] = 0;
dfs1(1,1);
dfs2(1);
while(Q–){
scanf(“%s”,op);
if(op[0] == ‘Q’){
printf(“%I64d\n”,ans*2);
}
else {
int id ;
scanf(“%d”,&id);
id–;
u = link[id];
val[u] ^= 1;
CHANGEU = u;
while(u)
u = ch[col[u]].change(u);
}
}
}
return 0;
}
