[BeiJing2010组队]次小生成树 Tree

[BeiJing2010组队]次小生成树 Tree

Time Limit:10000MS  Memory Limit:65536K
Total Submit:319 Accepted:40
Case Time Limit:1000MS

Description

小 C 最近学了很多最小生成树的算法,Prim 算法、Kurskal 算法、消圈算法
等等。
正当小 C 洋洋得意之时,小 P 又来泼小 C 冷水了。小 P 说,让小 C 求出一
个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:
如果最小生成树选择的边集是 EM,严格次小生成树选择的边集是 ES,那么
需要满足:(value(e) 表示边 e的权值)

这下小 C 蒙了,他找到了你,希望你帮他解决这个问题。

Input

第一行包含两个整数N 和M,表示无向图的点数与边数。
接下来 M行,每行 3个数x y z 表示,点 x 和点y之间有一条边,边的权值
为z。

Output

包含一行,仅一个数,表示严格次小生成树的边权和。(数
据保证必定存在严格次小生成树)

Sample Input

5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6

Sample Output

11

Hint

数据中无向图无自环;
50% 的数据N≤2 000 M≤3 000;
80% 的数据N≤50 000 M≤100 000;
100% 的数据N≤100 000 M≤300 000 ,边权值非负且不超过 10^9

Source
囧。。我知道这个题目可以用类似Tarjan的算法搞出来。但我悲剧的发现DFS在八中OJ上肯定爆栈囧。。只好用那种倍增的来做了。。反正复杂度都一样的(因为瓶颈不是这个而是MST)。。因为这样可以BFS。。
随便写个MST算出最小生成树,然后枚举每一条非树边,算出这个点在树上对应路径的最大边和次大边,如果跟最大边一样就跟新次大边,否则跟新最大边就OK了。。
用倍增的方法可以很容易的搞定这个。。
关键是TLE囧。。从AC大神牛哪里抄了份Specil Read过来。。总算过了囧。。
Code:
www.ideone.com/y9EAX

SGU 512. Friendly Points

给你N个点,求所有这样的点对:它们构成的四边形中没有其它点。。
额。。只有25个人AC。。但我发现并不是很难。。至少没有其它几道那么变态。。
我的想法是分治算法,把所有点分成左右两份的话可以做到在NLogN的时间统计跨越两边的点对。。然后分治一下。。就是NLogN^2了。。。
Code:
www.ideone.com/NwuV9

Zju2116 Christopher’s Christmas Letter

Zju2116 Christopher’s Christmas Letter

Time Limit:1000MS  Memory Limit:65536K
Total Submit:4 Accepted:3

Description

给定n个元素,要从中间选择m个元素有多少种方案呢?答案很简单,就是C(n,m)。如果一个整数m(0≤m≤n),C(n,m)是某一个质数p的倍数, 那么这个m就是讨厌的数字,现在给定了p和n,求有多少个讨厌的数字。

Input

第一行是一个正整数n,(1≤n≤10100)。
输入的第二行是一个质数p(1≤p≤107)。

Output

只有一行,表示讨厌的数字的个数。

Sample Input

6
2

Sample Output

3

Hint

30%的数据里,n≤1000;
100%的数据里,n≤10^100

Source

By Zzy
数学题。。我证了半天证明了设n的p进制表示为a0a1a2a3不讨厌的数字个数就是
(a0+1)*(a1+1)*(a2+1)。。。然后减一下就可以了。。
证明过程主要是因为打不出公式很难发出来。。主要是利用多项式的拆分。。

SPOJ 3974. Another Tree Problem

最近有点颓废啊。。刚刚写了这道题。。题目就是说给一颗代权树,每条路径的权值为上面所有边权的乘积,求每条路径的权值和。。
很显然对于这种复杂的计算树的路径的问题用树的分治就OK了。。一般来说写个基于点的分治就可以了。。
确实可以了。。
另外除法的时候注意一下最好还是用求拟元比较方便。。八中OJ上面那个A不掉囧。。SPOJ上能A掉。。
Code:
http://www.ideone.com/qMhjp

上篇的题解

额。。今天才发囧掉了。。最近太颓废了。。
(1):F(n+1)=(n+1)Fn-C(n,2)Fn-2..
(2):n*2^(n-2)
(3):9个。。构造和证明很麻烦就不说了。。
(4):16个。。证明非常麻烦。。
(5): C(2*n,n)^2
(6):提示,将正多边形的顶点编码成2进制。
(7):设F(x)=x二进制中1的数量,2^F(n)

数学夏令营

毕业旅游回来之后立马去参加浙江数学夏令营了囧。。。又要弄半天。。快没时间搞OI了悲剧。。那个什么块状树的东西只好先放放啦囧。。。
数学夏令营太无聊了。。今天的那个老师太SB啦!上课的时候动不动就颓废半小时,我强烈认为他自己都不知道题目怎么做。。幸好讲的是组合计数,还有一点意思,有几题挺有OI的感觉的额。。。
(1)。。N个字母,每个字母可以用两次,组成N对的方法有几种,可以自己配自己
翻译成图论,N个顶点的有标号图,每个顶点2度,有几个?(可以自环)。。。给个递推式就OK。。
(2)。。一个圆上N个点,一条经过每个点一次的不自交的折线有几种?
(3)。。N个人去参加夏令营做考试,考试有4道选择题,每个题目有3个选项,其中任三个人都有一道题目选的都不一样。。求N的最大值。。(这题相当BT。。)
(4)。。N*N的棋盘上放K个车,把被车占或攻击的格子称为危险的,同时每个车被拿掉后必然至少有一个格子由危险变为不危险,求K的最大值。。。
(5)。。蜗牛在无穷大的1*1方格组成的棋盘上,爬2*N步后回到原点,求方法数,给个公式?
(6)。。一个N维正方体,有2^N次方个顶点,设为A,B是A的子集,且|B|>[2^(N+1)]/N。求证B中必然有3个点构成正三角形。。。
(7)。。帕斯卡三角形第N行奇数有几个?给个公式。。
听人说那个老师是2届IMO金牌得主。。我深深的震惊了。。

QTREE

用上题几乎一样的代码无压力AC嘻嘻。。。
Code:
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#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 inf=~0U>>1,maxn=10000;
using namespace std;
vector<int> E[maxn],Et[maxn];
int T[maxn*2],C[maxn*2],mnt;
typedef vector<int>::iterator it;
int n,w[maxn],Lim,dep[maxn],Fa[maxn],P[maxn];
int own[maxn],Max[maxn],Sum[maxn]={};
void Build(int x,int f,int d)
{
dep[x]=d;Fa[x]=f;
int t,c,tmp=own[x];
tr(e,E[x])
{
t=T[*e],c=C[*e];
if(t==f)continue;P[*e/2]=t;
w[t]=c;if(Sum[tmp]++<Lim)own[t]=tmp,Et[x].pb(t);
Build(t,x,d+1);
}
}
void Dfs(int t,int m)
{
Max[t]=m=max(m,w[t]);
tr(e,Et[t])Dfs(*e,m);
}
void Change(int t,int u)
{
w[t=P[t]]=u;
if(t==own[t])Dfs(t,-inf);
else Dfs(t,Max[Fa[t]]);
}
int QMax(int a,int b)
{
int m=-inf;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b])
m=max(m,w[a]),a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
m=max(m,Max[a]),a=Fa[own[a]];
}
}
return m;
}
void AddEdge(int s,int t,int c)
{
T[mnt]=t;C[mnt]=c;
E[s].pb(mnt);mnt++;
}
void Init()
{
scanf(" ");
scanf("%d",&n);int s,t,c;
rep(i,n)E[i].clear(),Et[i].clear();
mnt=0;w[0]=-inf;
rep(i,n-1)
{
scanf("%d%d%d",&s,&t,&c);
–s;–t;
AddEdge(s,t,c);AddEdge(t,s,c);
}
}
void Solve()
{
Init();
Lim=sqrt(n)+1;
rep(i,n)own[i]=i,Sum[i]=1;
Build(0,-1,0);rep(i,n)if(own[i]==i)Dfs(i,-inf);
char cmd[100];int s,t;
for(;;)
{
scanf(" ");
scanf("%s",cmd);
if(cmd[0]==’D’)return;
scanf("%d%d",&s,&t);
if(cmd[0]==’Q’)printf("%dn",QMax(s-1,t-1));
else Change(s-1,t);
}
}
int main()
{
//freopen("in","r",stdin);
int t;scanf("%d",&t);
rep(i,t)Solve();
}

毕业旅游。。

   (*^__^*) 嘻嘻这几天我们三班的同学一起弄了个毕业旅游,庆祝我们毕业了吧。。
   头一天晚上吃晚饭的时候我在那边酗酒,结果酒量太差还装那啥,喝得大醉囧,然后一帮人就跑去唱歌,我这个五音不全的也去唱了几首,本来想去吼Linkin Park的歌的,发现都没有晕,只好乱唱了。。太难听了囧。。。凯哥跟陈雨萌还有Shirly和张天叶都是麦霸级别的啊,唱得超High囧,我本来很醉,但到后半夜就清醒了囧,就看到Fiona睡在金洋的身上,而且Fiona的衣服上是OWME(不解释。。)。。
   然后很悲剧的发现没有带笔记本电脑,只好玩我老婆了(就是我手机囧。。)。。。
   第二天好像是去吃烧烤了?我酒喝多了记不清楚了,烧烤还是蛮有意思的,就是我完全不会烧囧。。只好吃白食,老大跟Van都很会烧啊囧。。。后来好像下雨了。。然后下午就去玩那个什么XX洞了,我发现我老了,什么都记不清楚了囧。。。洞的名字都忘了。。没什么好说滴。。然后晚上一开始不想喝酒,不知怎么的就狂喝起来了。。然后又大醉,那帮人混宿去了,我在我房间睡地跟猪一样囧。。。
   第三天早上去秦王宫,被那个什么梦回秦汉的剧雷到了,然后下午去玩梦幻谷,那个地方还真不错,各种个样的设施都挺刺激滴,我很开心地坐了个遍,爽唉。。最囧的是在坐一个神奇的360度旋转的那个设施的时候。。我在那边大喊“徐XX我爱你。。”(不解释。。。)。。老大居然跟着我喊。。。。
   大家都是一对一对的(*^__^*) 嘻嘻,具体的就不说啦,我跟边远两个老男人在那边颓废,本来还想跟他去酗酒的。。这个家伙居然退缩了。。第三天晚上难得没有酗酒。。于是跟桑普他们打牌到深夜囧。。。
   流水账。。。流水账。。。
   第四天的话早上去一个XXX风景区-名字我又忘了。。打水仗什么的,然后我被人围攻湿透了。。半天才干囧。。。下午去漂流。。两个人一组。。本来是挺Happy的。。但最后悲剧大发。。一开始大家计划围攻老大跟XXX,结果这两个人逃到最后去了。。我跟奔奔一个组合。。都是轻量级的囧。。一开始几个道都挺刺激滴。。不过我在那边大喊毫无压力。。然后MS我看到Leo的船翻了。索性没事。。然后据需往前啊。。往前。。我跟跟奔奔准备在哪里偷袭老大跟XXX,结果看到一对小情侣翻掉了。。再一看是桑普跟胡嘉逸。。我跟奔奔还表示毫无压力。。结果之后就大悲剧了。。先是因为船漏气耽搁了半天,然后船被石头卡住了。。这个情况非常的囧。。旁边一个人都没有。。并且如果我跟奔奔不压住船船就要翻掉。。。最后我跟奔奔跑下去推船。。然后船动了。。我没来得及上去。。在水里扑腾了半天。。差点淹死囧。。最后奔奔大发神威把握拉上去喱。。接着我们以为就可以毫无压力了。。结果老是卡住。。其中一次奔奔没来得及上船。。然后我们两个只好喊人帮忙。。累个半死。。。傍晚一帮人开联谊会的。但我太累了就在那边休息。。。
    然后我回到酒店。。借了老大的手提在这里打流水账囧。。。

[ZJOI2008]树的统计Count

[ZJOI2008]树的统计Count

Time Limit:10000MS  Memory Limit:165536K
Total Submit:116 Accepted:61
Case Time Limit:1000MS

Description

一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作:
I. CHANGE u t : 把结点u的权值改为t
II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意:从点u到点v的路径上的节点包括u和v本身

Input

输入的第一行为一个整数n,表示节点的个数。
接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有一条边相连。
接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。
接下来1行,为一个整数q,表示操作的总数。
接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在 -30000到30000之间。

Output

对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

Source
额。。我的算法极慢,卡着时间过了。。
一般的算法就是Link—Cut树,树链剖分啊什么的,由于我太菜,只好想了个很SB的算法,我想的是可以不可以用类似于块状数组的办法来解决这道题目。。那么把这个树分成Sqrt(N)左右的小块,然后每次往上跳。。可以在Sqrt(N)中解决问题。。关键是怎么划分。。我TLE了N次主要就是在尝试划分的办法囧。。搞了半天最后稀里糊涂弄出来了。。我真是菜死了囧。。。
改进了一下Code。。变快一点了。。
Code:

#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#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 inf=~0U>>1,maxn=30000;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],Lim,dep[maxn],Fa[maxn];
int own[maxn],Max[maxn],Sum[maxn]={};
void Build(int t,int f,int d)
{
dep[t]=d;Fa[t]=f;
if(own[t]==-1)
{
own[t]=t;
Sum[t]++;
}
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(Sum[tmp]<Lim)
{
Et[t].pb(*e);
own[*e]=tmp;
Sum[tmp]++;
}
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
Sum[t]=s+=w[t];Max[t]=m=max(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,Sum[Fa[t]],Max[Fa[t]]);
}
int QSum(int a,int b)
{
int s=0;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b]||own[a]==a)
s+=w[a],a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
s+=Sum[a],a=Fa[own[a]];
}
}
return s+w[a];
}
int QMax(int a,int b)
{
int m=-inf;
while(a!=b)
{
if(dep[a]<dep[b])swap(a,b);
if(own[a]==own[b])
m=max(m,w[a]),a=Fa[a];
else
{
if(dep[own[a]]<dep[own[b]])swap(a,b);
m=max(m,Max[a]),a=Fa[own[a]];
}
}
return max(m,w[a]);
}
int main()
{
//freopen("in","r",stdin);
scanf("%d",&n);int s,t;Lim=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);
memset(own,-1,sizeof own);
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else if(cmd[1]==’S’)printf("%dn",QSum(s-1,t-1));
else printf("%dn",QMax(s-1,t-1));
}
}

Page 3 of 41234