这个变态题目。。有N种做法。。能AC的MS不多囧。。
做法系列1：
思路：从下往上对每个节点维护一个平衡树，然后用平衡树来回答第K大大问题
A:平衡树+启发式合并，两颗平衡树合并直接暴力把小的插进大的。。每个最多被插LogN次。。总共就是O(NLogN^2+QLogN)。。极难AC。。我Treap TLE，SBT也TLE。因为我SBT写得太烂了。。
B:Splay合并，Splay可以做到在O(NLogN)完成合并。。然后Splay常数较大，还是TLE。。。
C:注意题目的特性。。首先就是Q比N小很多，就是说许多结点都不需要维护平衡树，先先序遍历这个树，然后一些节点要插入的话直接用先序遍历中的区间插入。。再设个常数如果一个节点中最大的子树实在太小的话插入也麻烦干脆直接重新建个平衡树好。。估计可以勉强AC。。不过可能很困难吧。。我一直觉得可能可以弄个阀值仿照IOI2009的Region搞出来。。不过很麻烦。。
做法系列2：
思路：从小到大加入每个数，对每个节点维护还需要+几个数就可以输出了。。然后每次都可以取路径中的最小值，如果是0的话就输出，然后变成下一个。。一个节点显然只能影响的它的所有祖先。。所以需要维护路径。。
A:维护路径，还要最小值，直接上动态树，我的动态树写得太烂了。。无法AC。。。
B:维护路径也可以树链剖分啊，还是TLE。。。
做法系列3：
思路：TMD，干脆忽略这个树直接上区间K大值的算法好了，当然要先先序遍历一下了。。
A：一般的先二分在用线段树的做法肯定TLE O(NLogN+QLogN^3)..
B : 有一种二分树就是对所有权值建树，然后每个节点储存当前权值区间中的所有数在序列中的位置。。那么可以LogN得到节点区间中L到R之间的树的个数，就可以在LogN^2完成2分了。。写的好一点可以AC。。。
C：还有一种很NB的划分树，可以在NLogN+QLogN的时间解决问题。。非常NB啊。。具体看www.notonlysuccess.com/ 还不会写哎。。不过应该可以AC。。。

哎。。真是一场失败的SRM。。Rating没变囧。。
Level I
这么一道水题我只有235分。。实际上只要枚举就行了。但比赛前最后3分钟我发现我的KawiEdit不能用了晕。。结果拼命抢修。。修好后一慌张手速就慢了。。而且我看到这题后立马写二分。。脑缺死了。。n这么小干嘛不枚举啊晕。。
Level II
这个题目太恶心了。。本来我想的完全正确啊。。代码也没有错（一开始我一直以为我概率搞错。。最后发现是题目恶心）。。注意到每个人的friend字符串在36个字符以下。。那么算一下可以发现一个人最多有15个朋友。。关键是题目中有一句话说主人公只会访问自己的朋友。。所以顶点数最多16！！！靠。。
那么就简单了设Dp(Vised,int last)表示访问过了Vised的人，最后一个是last。。首先枚举下一个是哪个。。然后按概率排序。。显然第i个被主人公选择的情况只可能是前i-1个都不幸悲剧了。。第i个又OK。。那么算出这个概率然后+起来就OK了。。
Level III
额。。这题实际上不是非常难啊晕。。我当时完全没有时间去做了悲剧。。
首先注意到这个图是个仙人掌，所以一条边要么是桥要么在一个环里面额。。是桥的话显然要是crewSize。。否则的话考虑这个环，加入这个环离出口最近的是0，其它一次标号为1..n，那么首先如果没有Cabin的话，设L[x]是x到x-1,R[x]是x到x+1的Cabin数量，显然L[x]+R[x]>=crewSize。并且如果L[x]>L[x-1]完全没意义。。所以L[x]<=L[x-1]同理R[x]<=R[x+1]..然后现在有一些Cabin。。那么就跟一个经典问题就是把一个数列通过最小的变换变成单调类似了。。注意到降低显然不需要费用。。那么就OK了。。

应某人要求将名字改成X哥。。扯蛋的时候现编的题目。。感觉很有意思啊。。
2.X哥的泡妞计划
(paoniu.in/paoniu.out)
英俊潇洒玉树临风的X哥要开始泡妞啦！X哥看上了N个妞比如XX，XXX，XXXX，泡妞，当然是要花钱滴！第i个妞要花掉X哥Vi的钱，可有些女生之间风格差别太大比如XX和XXXX，X哥无法适应囧,因此就不能一起泡啦，有M对这样的女生，第i对是ai和bi。。X哥的母亲知道了这个消息，觉得自己儿媳妇自然是越多越好。。于是给了X哥V的钱，让X哥去泡妞！X哥最多能泡几个妞呢？
数据范围
N<=100 X哥看上的女生不会太多。。
M<= 200
V<= 1000
输入：
第一行是N和M和V
第二行有N个数，分别是Vi
之后每行一对ai和bi

感谢大家来踩

给一个素数p，整数k和a
就x^k=a(mod p)的所有整数解。。。
首先算出原根g
设x=g^i(mod p)
则首先若a==0(我就是忘处理这个所以WAN次囧。。)。。那么答案就是0.。
否则a=g^j(mod p)
那么g^(ik)=g^j
<=> ik=j(mod p-1)..
算出所有满足这个的i，代入得到所有x，排序就OK了。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=20;
using namespace std;
typedef long long ll;
ll P[maxn],m=0,p,g,k,a;
void decompose(ll x)
{
for(ll i=2;i*i<=x;i++)
if(x%i==0)
{
P[m++]=i;
while(x%i==0)x/=i;
}
if(x>1)P[m++]=x;
}
ll ext_gcd(ll a,ll b,ll&x,ll&y)
{
if(!b){x=1;y=0;return a;}
ll tmp=ext_gcd(b,a%b,y,x);y-=x*(a/b);
return tmp;
}
ll pow(ll x,ll e)
{
if(!e)return 1;
ll tmp=pow(x,e/2);tmp*=tmp;tmp%=p;
if(e&1)tmp*=x,tmp%=p;
return tmp;
}
ll inv(ll x)
{
return pow(x,p-2);
}
bool IsRoot(ll a)
{
rep(i,m)
if(pow(a,(p-1)/P[i])==1)return false;
return true;
}
void FindRoot()
{
decompose(p-1);
for(ll i=2;i<p;i++)if(IsRoot(i)){g=i;break;}
}
ll discrete_Log(ll a)
{
map<ll,ll> Map;ll M=sqrt(p)+1;
ll v=inv(pow(g,M));
ll e=1;Map[1]=0;
for(ll i=1;i<M;i++){e=e*g%p;if(!Map.count(e))Map[e]=i;}
for(ll i=0;i<M;i++)
{
if(Map.count(a))return i*M+Map[a];
a=a*v%p;
}
return -1;
}
vector<ll> Solve(ll a,ll b,ll m)
{
ll x,y,d;
d=ext_gcd(a,m,x,y);
vector<ll> A;
if(b%d)return A;
ll t=b/d;x%=m;if(x<0)x+=m;x=x*t%m;
rep(i,d)
{
A.pb(x);
x+=m/d;x%=m;
}
return A;
}
int main()
{
//freopen("in","r",stdin);
cin>>p>>k>>a;
if(a==0){cout<<1<<endl<<0<<endl;return 0;}
FindRoot();
ll Loga=discrete_Log(a);
vector<ll> Logx=Solve(k,Loga,p-1);
cout<<Logx.size()<<endl;
vector<ll> Ans;
tr(it,Logx)
{
ll tmp=pow(g,*it);
Ans.pb(tmp);
}
sort(Ans.begin(),Ans.end());
tr(it,Ans)cout<<*it<<endl;
}

[CROATIAN2009]OTOCI

Time Limit:50000MS  Memory Limit:165536K
Total Submit:22 Accepted:20
Case Time Limit:5000MS

Description

给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作：
1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。
2、penguins A X：将结点A对应的权值wA修改为X。
3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B的路径上的点对应的权值的和。
给出q个操作，要求在线处理所有操作。
数据范围：1<=n<=30000, 1<=q<=300000, 0<=wi<=1000。

Input

第一行包含一个整数n(1<=n<=30000)，表示节点的数目。
第二行包含n个整数，第i个整数表示第i个节点初始时对应的权值。
第三行包含一个整数q(1<=n<=300000)，表示操作的数目。
以下q行，每行包含一个操作，操作的类别见题目描述。
任意时刻每个节点对应的权值都是1到1000的整数。

Output

输出所有bridge操作和excursion操作对应的输出，每个一行。

Sample Input

5
4 2 4 5 6
10
excursion 1 1
excursion 1 2
bridge 1 2
excursion 1 2
bridge 3 4
bridge 3 5
excursion 4 5
bridge 1 3
excursion 2 4
excursion 2 5

Sample Output

4
impossible
yes
6
yes
yes
15
yes
15
16

Source
这题做法很多啊。。有动态树、DFS序之类的。。我的算法是最傻叉的一种。。因为我非常的傻叉。。所以我写了个树链剖分来做这个。由于只要求和所以上树状数组就OK啦。。不过由于有+边的操作。。于是设定一个询问耗时上限，如果超过上限就重新剖分，然后+边就直接暴力+就可以了囧。。
Code：
www.ideone.com/ZAZvq

题目就是给你一颗树，每次两个操作，一个是询问A到B的路径上边权的最大连续和，还有一个就是将一条路径所有边权修改成一个数。。。
树链剖分。。像一般线段树那样维护4个值。。。还有打标记。。
我写好之后翻了一下oimaster的park的代码。。对神牛的Orz之情如长江之水绵延不绝啊。。。不过我发现我的写法有点诡异。。我好像是完全忽略轻边直接全部都是线段树的。。所以速度好像慢很多囧。。不过似乎好写一点囧。。还有就是在线段树我直接按深度范围当区间了。。
最近树的题目做的好多啊。。接下来去做OTOCI还有QTREE的其他几道好了囧。。
我发现我GSS系列的题目只差GSS2了。。
Code：
www.ideone.com/qoxC6

月下“毛景树”

Time Limit:20000MS  Memory Limit:65536K
Total Submit:77 Accepted:15
Case Time Limit:2000MS

Description

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。
毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着 他最爱吃的毛毛果~~~
“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛 毛果的个数：
 Change k w：将第k条树枝上毛毛果的个数改变为w个。
 Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
 Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。
由于毛毛虫很贪，于是他会有如下询问：
 Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

Input

第一行一个正整数N。
接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。
接下来是操作和询问，以“Stop”结束。

Output

对于毛毛虫的每个询问操作，输出一个答案。

Sample Input

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

Sample Output

9
16

【Data Range】
1<=N<=100,000，操作+询问数目不超过100,000。
保证在任意时刻，所有树枝上毛毛果的个数都不会超过10^9个。

Source

绍兴一中
没什么好说的。裸的树链剖分。。为了战胜TLE我搞的累死。。最后发现几处地方写错了。。囧。。。线段树维护的时候维护两个标记Add和Same具体操作看代码吧囧。。
我这个干脆就给每个线段树开了个内存池然后变成纯数组了。。。。非常的猥琐。。
Code：
www.ideone.com/oEXcP

Spoj 3974 3974. Another Tree Problem

Time Limit:1000MS  Memory Limit:65536K
Total Submit:13 Accepted:2

Description

As you are bound to know by now, a tree is a connected graph
consisting of N vertices and N−1 edges. Trees also have the property
of there being exactly a single unique path between any pair of
vertices.
You will be given a tree in which every edge is assigned a weight –
a non negative integer. The weight of a path is the product of the
weights of all edges on the path. The weight of the tree is the sum of
the weights of all paths in the tree. Paths going in opposite
directions (A to B and B to A) are considered the same and, when
calculating the weight of a tree, are counted only once.
Write a program that, given a tree, calculates its weight modulo 1000000007.

Input

The first line contains the integer N (2 ≤ N ≤ 100 000), the number of vertices
in the tree. The vertices are numbered 1 to N. Each of the following N−1
contains three integers A, B and W (1 ≤ A, B ≤ N, 0 ≤ W ≤ 1000)
describing one edge. The edge connects vertices A and B, and its weight is W.

Output

Output the weight of the tree, modulo 1000000007.

Sample Input

3
3 2 100
2 1 100

Sample Output

10200

Hint

The weight of the path from 1 to 2 is 100
The weight of the path from 2 to 3 is 100
The weight of the path from 1 to 3 is 100 * 100 = 10000
So the weight of the tree is 10000 + 100 + 100 = 10200

Source
靠。。由于我毫无智商。。。这个题目很显然Dfs一下就可以解决了。。但我以前居然写个树的分治去做。。我真是脑缺啊囧。。。。
是在太鄙视自己了。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(eit e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=100000,mod=1000000007;
using namespace std;
typedef long long ll;
int n;
struct Edge
{
int t,c;
Edge(int _t,int _c):t(_t),c(_c){}
};
vector<Edge> E[maxn];
typedef vector<Edge>::iterator eit;
void InsEdge(int s,int t,int c)
{
E[s].pb(Edge(t,c));E[t].pb(Edge(s,c));
}
ll pow(int x,int e)
{
if(!e)return 1;
ll tmp=pow(x,e/2);tmp*=tmp;tmp%=mod;
if(e&1)tmp*=x,tmp%=mod;
return tmp;
}
ll Sum[maxn],P,ans=0;
int Q[maxn],F[maxn],h,t;
void BFS(int vs)
{
h=t=0;
for(Q[t++]=vs,F[vs]=-1;h<t;h++)
{
int x=Q[h];
tr(e,E[x])if(e->t!=F[x])
F[e->t]=x,Q[t++]=e->t;
}
for(int i=h-1;i>=0;i–)
{
int x=Q[i];Sum[x]=1;
ll all,tmp,ret=0;
tr(e,E[x])if(e->t!=F[x])
Sum[x]+=Sum[e->t]*e->c,Sum[x]%=mod;
all=Sum[x]+1;
tr(e,E[x])if(e->t!=F[x])
tmp=Sum[e->t]*e->c,tmp%=mod,ret+=(all-tmp)*tmp,ret%=mod;
ret*=P;ret%=mod;if(ret<0)ret+=mod;ans+=ret;ans%=mod;
}
}
int main()
{
//freopen("in","r",stdin);
cin>>n;int s,t,c;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);–s;–t;
InsEdge(s,t,c);
}
P=pow(2,mod-2);
BFS(0);
cout<<ans<<endl;
}

天哪。。我是个大傻叉！！！
我的路径剖分写的比我那个块状树还要慢！！！！！
我要撞死了囧。。。
就是一般的路径剖分。。就是写的太疵了。。
代码写了200行囧啊。。。
Code：
www.ideone.com/r9MQf