今天真是太悲剧了。。。第一题想了半天才弄出来结果被Cha掉了。。全房间唯一一个被Cha的。。然后其它题目脑缺全部不会做。。。0分。。。。

第一题不会捉。。。爆搜。。
第二题不会捉。。。爆搜。。
第三题不会捉。。。爆搜。。
没了。。

好吧这些题目也太水了囧。。。
Problem A 此题亮瞎我的狗眼
Problem B 此题再次亮瞎我的狗眼
Problem C 这题每次用输入的边更新一下每对点之间的最短路在求和就可以了。。
Problem D 每次找一条在环中的边，把它删掉，再把两个联通块连起来。。
Problem E 先把所有被包含的删掉（如果全部都一样的话特判一下。。）。。用Hash算出每对之间最大重合长度。。随便搜索一下就OK了。。

不得不说ZKW天牛的线段树实在是太NB了。。
我最近闲的无聊用这个改写了个ZJOI的Count。。结果刷到了Rank 1囧。。
然后去写QTREE。。刷到了第7囧。。
我又去研究了半天。。发现这样的写法子底向下也有悲剧的地方就是如果一定要需要区间标记，就没办法了。。不过也是蛮好解决的，由于每层最多两个区间，所以一遍走过把它们全部记录下来，然后对它们从上往下处理，有标记就往下推就可以了。。
这种写法的线段树实在太帅了。。几乎无常数，比递归快N多。。。。
Orz zkw天牛！！！！！！！！！！！！！！！！

我参加的是网上公开赛囧。。不过比赛还没结束就写这个会不会判作弊啊囧。。
Problem 1
题意就是对所有1<=i<=n,1<=j<=m算出(i,j)*2-1的和
额。。皇上，还记得大明湖畔的。。。
额。是POI的ZAP么。。
枚举(i,j)用一样的方法算出这样的对数，就OK了。。
好吧暴力可以拿80分。。汗。。
Problem 2
恩。。这题非常的猥琐啊。。
先求出前缀和。。设为S好了。。
考虑区间(l,r]固定r那么l的范围就是[r-R,r-L]。。
然后如果能对每个r用一种办法可以得出下一个最大的以r结尾的区间权值的话，就可以用类似表归并的
办法搞出前K大区间了。。
权值和等于S[r]-S[l]。。故只需要用区间K大值的办法来维护。。。
但数据范围很大啊。。。
我一开始写了个LogN^2的，手测TLE囧。。
然后在第三题毫无思路的情况下豁出去了。。写了个划分树。。自己机子上最大数据2s多一点。。测评机应该比我电脑强吧囧。。。
关键是这里所有查询区间的长度都是一样滴。。不过我不知道怎么用哎。。。
Problem 3
这题我纯属直觉，首先所有点高度在[0,1]。。然后我根据直觉强行认为所有点要么0要么1（就可以最小割了。。否则没法做啊。。）。。然后发现最小割对于最大数据会TLE。。很明显可以想到八中OJ的第二题。。考虑转化成对偶图。。我毫无根据的抛弃后一半输入数据。。然后建个图写了个Dijstra。。为此自己手写了个Vector，手写了个Heap囧。。。然后写了个网络流对拍。。发现没什么问题。。于是就交掉了。。。

去参加了NOI2010的网上公开赛。。。。搞好了之后吃完了饭就去oibh灌水。。。瞎逛了半天无意间看到了这个东西。。非常的NB啊。。当时我就震惊了。。
http://aceeca1.frostbytez.com/index.php/archives/线段树全接触

这是道好题啊。。。想想麻烦。。做做更麻烦。。
题目很简洁，给你一个图，求哪些边删掉之后能变成二分图。。
额。。我WA了N次。。比赛的时候肯定来不及。。。
慢慢分析吧。。
首先求生成树，然后对每个点2-染色，
那么如果删非树边的话，显然任何点的颜色都不会变，那么如果两端颜色一样的非树边有0条，所有非树边都可以删，有1条，只有这条可以删，2条或以上，都不能删。。
如果删树边的话，显然必须要搞翻所有的奇环，分析一下什么情况下一个树中会出现奇环。。
某个两端颜色一样的非树边造成的奇环。。
一个两端颜色一样的非树边和一个两端不一样的非树边造成的奇环。。
那么把这个树树链剖分一下。。对每个两端颜色一样的非树边的两点之间的路径+1，显然要删的树边上的权值一定要等于非树边的数量。。
然后对每个两端颜色不一样的非树边的两点之间的路径+1，显然要删掉树边不能在被两端颜色一样的非树边的两点间的路径跨越的情况下再被这个不一样的非树边的两点之间的路径跨越。。
然后维护两个树链剖分。。分别搞树边和非树边。。就没什么问题了。。
写的累死晕。。。
我发现还是我在codeforces上英文的说明更清楚一点啊囧。。。
It’s a interesting problem.If you for every edge, 
try to remove it and check if it is a bipartite 
graph..I think it will get TLE..so let’s analysis 
the property of bipartite graph..
It should never contain a cycle of odd length…
and it can be 2-colored..
so first build a spanning forest for the graph..
and do the 2-color on it(Tree can be 2-colored).
for convenience.
Let TreeEdge={all edge in forest}
NotTreeEdge={All edge}/TreeEdge
ErrorEdge={all edge that two endpoint have the same color..}
NotErorEdge=NotTreeEdge/ErroEdge..
First,consider a edge form NotTreeEdge,remove it 
can’t change any node’s color..so..if |ErrorEdge|=0 of course we can remove all NotTreeEdgeif =1 we just can remove the ErrorEdgeif >1 we can’t remove any from NotTreeEdge
Now,Let consider a Edge e from TreeEdge..
Let Path(Edge e)=the path in forest between e’s two endpoints..
if there is a Edge e’ from ErrorEdge that Path(e’) 
didn’t  go through e..it will destroy the bipartite 
graph..
if there is a Edge e’ from ErrorEdge that Path(e’) go through e and there is a Edge e” from NotErrorEdge that Path(e”) go through e..it will also destroy the bipartite graph..
so now we need to know for every edge,how many such path go through it..it require a data structure…
one way is to use heavy-light decomposition then we can update every path in O(LogN^2)…
another way is to use Link-Cut Tree..It can do the same in O(LogN)….
Code：
http://www.ideone.com/dPS5N

自己做了场CodeForces。。发现偏偏是没有题解的那个囧。。。
A：跟24的B有点像的繁琐题。。忽略吧。。我由于过于SBWA了2次囧。。
B：将所有t=t+1，注意到选择的物品t的和要大于n。。同时价格和最小。。就是背包问题了。。
C：额。。显然每个repeat的开头那个跟中间那个是一样的，那么枚举每对一样的数，同时用Suffix Array帮忙算Lcp就可以搞出所有repeat，然后排个序依次处理就可以了。。为了方便我写了CQF的New Lcp。。
D：这个题目蛮有意思的。。首先要在尽量在右边，同时又要大于某个值，显然让人想到线段树。。所以我离散化了一下写了个线段树，同时对每个X值维护一个Set就可以了。。
E：有点难哎。。先睡觉吧明天再想啦

我震惊了。。

显然这次人品爆发的有点厉害。。话说每次我SRM的时候人品总会很好。。。这次好到了令人发指的程度。。。。
Problem 250 显然是水题，表示忽略。。
Problem 500 就是给你一堆数，每两个平方和是平方数的数能凑成一对，最对凑出几对？
我毫无思路。其实这个图是二分图那么就很显然了。。但很悲剧的是当时我想不出这个。。。。由于我信春哥。。我正好做过Ural 1099。。。于是写了个随机化交了。。居然过了。。
恩。。写个是二分图的证明吧。。
由于对两个数x,y来说,gcd(x,y)=1，所以不能都是偶数，同时一个数平方mod4只能是0或1.。显然如果两个都是1就不对了。。。所以只能一个是0一个是1，那么按平方mod4的余数分成两部分就可以了。。
Problem 1000 这题显然是APIO-2010巡逻那题的一个变种。。。所以同样算法可以无压力AC。。好像不能用O(n)的那个找直径的算法。。所以我写了个n^2的。。一开始写了个n^3的。。发现会TLE只好resubmit。。。
额。。差5分就可以变红了。。看来注定是个悲剧啊。。下次肯定没这么好RP就要掉Rating了。。。

最近过于颓废一直拖着这篇小论文囧。。今天总算不颓废了。。写下吧。。
称树的一个联通的顶点子集为树块，一个树块的根就是这个树块中深度最小的顶点，那么如果将树划分成一些树块
有如下定理：
对于两个顶点，(1)若他们属于相同的树块，那么Lca肯定在该数块中，(2)如果属于不相同的树块，Lca肯定不在树块的根较浅的那个树块中。。。
证明：(1)废话
(2)：否则Lca就会在另一个顶点与其树块的根的路径上，与Lca属于较浅的那个树块矛盾。。
现在以QTREE为考虑的问题。。
考虑QTREE，如果对每个点都维护其到其树块的根的路径上最大边权，那么我们的询问就可以用以下方法完成。。
设当前顶点是u、v
若在同一树块中，直接暴力..
否则可以使用维护的信息跳过一个树块。。
同时修改直接暴力可以解决。。
那么显然要让修改快，当然块越小越好，要让查询快，当然块越大越好。取个综合，就是Sqrt(N)了。。
那么就要搞出一种划分的方法使得，
每个块大小不超过SqrtN。。。
每个点到根最多经过SqrtN个块。。。
划分的方法有很多.。我想出来3个。。就说说最实用的那个吧。。
Dfs一下，对每个结点只要其属于的块大小不超过SqrtN，就把其孩子加入其属于的块。。否则其孩子自立一个块。。
这种数据结构的优点：
代码短，好写，没了。。
缺点：
只能维护单点（边）的修改，不能应付GSS7那样的神题，
速度：
速度还不错。。可以看下我交的那个八中OJ1036的代码。。。最快的那个第16。。。
写的时候的一些技巧：
修改的时候只需要修改该点在块里的后代，可以加快不少。
对每个点另开一个边表维护在块里的后代。
或者用Bfs来修改（快不了多少。。。）
代码：
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int maxn=30000,inf=~0U>>1;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],L,D[maxn],F[maxn];
int own[maxn],M[maxn],S[maxn]={};
void Build(int t,int f,int d)
{
D[t]=d;F[t]=f;
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(S[tmp]++<L)Et[t].pb(*e),own[*e]=tmp;
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
S[t]=s+=w[t];M[t]=m>?=w[t];
tr(e,Et[t])Dfs(*e,s,m);
}
void Change(int t,int u)
{
w[t]=u;
if(t==own[t])Dfs(t,0,-inf);
else Dfs(t,S[F[t]],M[F[t]]);
}
void Query(int a,int b,int&s,int&m)
{
s=0;m=-inf;
while(a!=b)
{
if(D[a]<D[b])swap(a,b);
if(own[a]==own[b])
s+=w[a],m>?=w[a],a=F[a];
else
{
if(D[own[a]]<D[own[b]])swap(a,b);
s+=S[a],m>?=M[a],a=F[own[a]];
}
}
m>?=w[a];s+=w[a];
}
int main()
{
scanf("%d",&n);int s,t;L=sqrt(n)+1;
rep(i,n-1)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)scanf("%d",w+i),own[i]=i;
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];int S,M;
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else
{
Query(s-1,t-1,S,M);
if(cmd[1]==’S’)printf("%dn",S);
else printf("%dn",M);
}
}
}