停课这几天天天考啊。。。QAQ

rating一蹦一跳的好虚啊

HNOI真心。。

同情

T1. 最小公倍数

Description	给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b的形式。 现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义： 最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。 路径：路径P:P1,P2,…,Pk是顶点序列，满足对于任意1<=i<k，节点Pi和Pi+1之间都有边相连。 简单路径：如果路径P:P1,P2,…,Pk中，对于任意1<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。
Input	输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。 接下来M行，每行包含四个整数u、v、a、b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。 接下来q行，每行包含四个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9
Output	对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余字母小写）
Sample Input	4 5  1 2 1 3  1 3 1 2  1 4 2 1  2 4 3 2  3 4 2 2  5  1 4 3 3  4 2 2 3  1 3 2 2  2 3 2 2  1 3 4 4
Sample Output	Yes  Yes  Yes  No  No
Hint

传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=4537

其实并查集还是挺好想到的吧

但是有了并查集还是要T飞啊

那怎么办呢

分块！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cstring>
#define NN 50010
#define MM 100010
using namespace std;
struct Edge
{
	int x,y,a,b,id;
}e[MM],q[MM],tmp[MM];
int fa[MM],n,m,sz[MM],Q,tot,ma[MM],mb[MM],block,k;
bool vis[MM]={0};
struct PRE
{
	int x,y,sz,fa,yma,ymb,f,xma,xmb;
}pre[MM];
void read(int &xx)
{
	bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
bool cmp1(Edge xx,Edge yy) { if (xx.a==yy.a) return xx.b<yy.b; else return xx.a<yy.a;}
bool cmp2(Edge xx,Edge yy) { if (xx.b==yy.b) return xx.a<yy.a; else return xx.b<yy.b;}
int Find(int xx) { return (xx==fa[xx]?xx:Find(fa[xx]));}
void Doit(int x,int y,int a,int b)
{
	int xx=Find(x), yy=Find(y);
	if (sz[xx]>sz[yy]) swap(xx,yy);
	pre[++tot].x=xx, pre[tot].y=yy, pre[tot].f=fa[xx], pre[tot].sz=sz[yy];
	pre[tot].yma=ma[yy], pre[tot].ymb=mb[yy], pre[tot].xma=ma[xx], pre[tot].xmb=mb[xx];
	if (xx==yy) 
	{
		ma[yy]=max(ma[yy],a), mb[yy]=max(mb[yy],b); return;
	}
	fa[xx]=yy, sz[yy]+=sz[xx], ma[yy]=max(ma[yy],max(ma[xx],a)), mb[yy]=max(mb[yy],max(mb[xx],b));
}
void Back()
{
	for (;tot;tot--)
	{
		fa[pre[tot].x]=pre[tot].f, ma[pre[tot].x]=pre[tot].xma, mb[pre[tot].x]=pre[tot].xmb;
		sz[pre[tot].y]=pre[tot].sz, ma[pre[tot].y]=pre[tot].yma, mb[pre[tot].y]=pre[tot].ymb;
	}
}
int main()
{
	read(n), read(m);
	for (int i=1;i<=m;++i) read(e[i].x), read(e[i].y), read(e[i].a), read(e[i].b), e[i].id=i;
	read(Q);
	for (int i=1;i<=Q;++i) read(q[i].x), read(q[i].y), read(q[i].a), read(q[i].b), q[i].id=i;
	sort(e+1,e+1+m,cmp1); sort(q+1,q+1+Q,cmp2);
	block=(int)sqrt(m);
	for (int i=1;i<=m;i+=block)
	{
		k=0;
		for (int j=1;j<=Q;++j) 
			if (q[j].a>=e[i].a && (i+block>m || q[j].a<e[i+block].a)) tmp[++k]=q[j];
		if (!k) continue;
		sort(e+1,e+i,cmp2);
		for (int j=1;j<=n;++j) fa[j]=j, sz[j]=1, ma[j]=mb[j]=-1;
		for (int j=1,t=1;j<=k;++j)
		{
			for (;t<i && e[t].b<=tmp[j].b;t++) Doit(e[t].x,e[t].y,e[t].a,e[t].b);
			tot=0;
			for (int l=i;l<i+block&&l<=m;++l)
			if (e[l].a<=tmp[j].a && e[l].b<=tmp[j].b) Doit(e[l].x,e[l].y,e[l].a,e[l].b);
			int xx=Find(tmp[j].x), yy=Find(tmp[j].y);
			if (xx==yy && ma[xx]==tmp[j].a && mb[xx]==tmp[j].b) vis[tmp[j].id]=1;
			Back();
		}
	}
	for (int i=1;i<=Q;++i) if (vis[i]) puts("Yes"); else puts("No");
	return 0;
}

T2. 网络

Description	一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。由于这条路径是唯一的，当路径上的某个服务器出现故障，无法正常运行时，数据便无法交互。此外，每个数据交互请求都有一个重要度，越重要的请求显然需要得到越高的优先处理权。现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也是很简单的，在每一个时刻，只有可能出现下列三种事件中的一种： 1.  在某两个服务器之间出现一条新的数据交互请求； 2.  某个数据交互结束请求； 3.  某个服务器出现故障。系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后，这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。你的任务是在每次出现故障时，维护未被影响的请求中重要度的最大值。 注意，如果一个数据交互请求已经结束，则不将其纳入未被影响的请求范围。
Input	第一行两个正整数n,m，分别描述服务器和事件个数。服务器编号是从1开始的，因此n个服务器的编号依次是1,2,3,…,n。接下来n-1行，每行两个正整数u,v，描述一条树边。u和v是服务器的编号。 接下来m行，按发生时刻依次描述每一个事件；即第i行（i=1,2,3,…,m）描述时刻i发生的事件。每行的第一个数type描述事件类型，共3种类型： （1）若type=0，之后有三个正整数a,b,v，表示服务器a,b之间出现一条重要度为v的数据交互请求； （2）若type=1，之后有一个正整数t，表示时刻t（也就是第t个发生的事件）出现的数据交互请求结束； （3）若type=2，之后有一个正整数x，表示服务器x在这一时刻出现了故障。对于每个type为2的事件，就是一次询问，即询问“当服务器x发生故障时，未被影响的请求中重要度的最大值是多少？”注意可能有某个服务器自身与自身进行数据交互的情况。
Output	对于每个type=2的事件，即服务器出现故障的事件，输出一行一个整数，描述未被影响的请求中重要度的最大值。如果此时没有任何请求，或者所有请求均被影响，则输出-1。
Sample Input	13 23  1 2  1 3  2 4  2 5  3 6  3 7  4 8  4 9  6 10  6 11  7 12  7 13  2 1  0 8 13 3  0 9 12 5  2 9  2 8  2 2  0 10 12 1  2 2  1 3  2 7  2 1  0 9 5 6  2 4  2 5  1 7  0 9 12 4  0 10 5 7  2 1  2 4  2 12  1 2  2 5  2 3
Sample Output	-1  3  5  -1  1  -1  1  1  3  6  7  7  4  6
Hint	解释其中的部分询问；下面的解释中用(a,b;t,v)表示在t时刻出现的服务器a和b之间的重 要度为v的请求： 对于第一个询问（在时刻1），此时没有任何请求，输出-1。 对于第四个询问（在时刻6），此时有两条交互(8,13;2,3),(9,12;3,5)，所有询问均经过2 号服务器，输出-1。 对于第五个询问（在时刻8），此时有三条交互(8,13;2,3),(9,12;3,5),(10,12;7,1)，只有交互 (10,12;7,1)没有经过2号服务器，因此输出其重要度1。 对于最后一个询问（在时刻23），此时有三条交互(9,5;12,6),(9,12;16,4),(10,5;17,7)。当3 号服务器出现故障时，只有交互(9,5;12,6)没有经过3号服务器，因此输出6。
Data Range

传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=4538

考试时只做了30分的程序真的不要怪我咯

%%%LCZ AK离场（树剖大师！

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cstring>
#include <set>
#define NN 100010
using namespace std;
struct A
{
	int x,y,t,v,type;
	bool fi;
	set <int> se;
}a[5050];
struct Edge
{
	int ne,u,v;
}e[NN];
int n,m,x,y,du[NN],maxd,head[NN],viss=0,tot=0,ans,que[NN],vis[NN],la[NN];
void read(int &xx)
{
	bool f=0; char CH;
	for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
	for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
}
void Build(int xx,int yy)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx;
	e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy;
}
void BFS(int xx,int yy,int k)
{
	int h=0,t=0;
	que[++t]=xx,la[t]=0,vis[xx]=++viss;
	bool flag=0;
	while (h<t)
	{
		++h;
		for (int i=head[que[h]];i;i=e[i].ne)
		if (vis[e[i].v]!=viss)
		{
			vis[e[i].v]=viss;
			que[++t]=e[i].v, la[t]=h;
			if (e[i].v==yy) {flag=1; break;}
		}
		if (flag) break;
	}
	for (int i=t;i;i=la[i]) a[k].se.insert(que[i]);
}
int main()
{
	read(n), read(m);
	for (int i=1;i<n;++i) read(x), read(y), Build(x,y), du[x]++, du[y]++, maxd=max(maxd,max(du[x],du[y]));
	
		for (int i=1;i<=m;++i)
		{
			read(a[i].type);
			if (a[i].type==0)
			{
				read(a[i].x), read(a[i].y), read(a[i].v);
				BFS(a[i].x,a[i].y,i);
			}
			else if (a[i].type==1)
			{
				read(a[i].t); a[a[i].t].fi=1; a[i].fi=1;
			}
			else if (a[i].type==2)
			{
				a[i].fi=1;
				ans=0;
				read(a[i].t);
				for (int j=1;j<i;++j)
				if (!a[j].fi)
				{
					if (!a[j].se.count(a[i].t)) ans=max(ans,a[j].v);
				}
				if (ans==0) puts("-1"); else printf("%d\n",ans);
			}
		}
	return 0;
}

标算树剖咯。弄个优先队列记录一下什么的

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 0x3f3f3f3f
#define NN 100010
using namespace std;
struct Edge
{
    int ne,u,v;
}e[NN<<1];
struct A 
{ 
    int x,y;
}a[110];
bool operator <(A xx,A yy) { return xx.x<yy.x;}
int n,m,num,numm=0,tot=0,ans=0,cnt,now,x,y,op;
int pos[NN],son[NN],fa[NN],sz[NN],deep[NN],head[NN],anc[NN];
bool flag[NN<<1];
priority_queue<A> que[300010];
int read()
{
    int xx; bool f=0; char CH;
    for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
    for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
    return xx;
}
void Build(int xx,int yy)
{
    e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx;
    e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy;
}
void DFS1(int xx)
{
    sz[xx]=1;
    for (int i=head[xx];i;i=e[i].ne)
    if (e[i].v!=fa[xx])
    {
        fa[e[i].v]=xx, deep[e[i].v]=deep[xx]+1;
        DFS1(e[i].v);
        sz[xx]+=sz[e[i].v];
        if (sz[e[i].v]>sz[son[xx]]) son[xx]=e[i].v;
    }
}
void DFS2(int xx,int chain)
{
    pos[xx]=++numm, anc[xx]=chain;
    if (son[xx]) DFS2(son[xx],chain);
    for (int i=head[xx];i;i=e[i].ne)
    if (e[i].v!=son[xx] && e[i].v!=fa[xx]) DFS2(e[i].v,e[i].v);
}
void Query(int k,int l,int r,int x)
{
    while (!que[k].empty() && flag[que[k].top().y]) que[k].pop();
    if (!que[k].empty()) ans=max(ans,que[k].top().x);
    if (l<r)
    {
        int mid=(l+r)>>1;
        if (x<=mid) Query(k<<1,l,mid,x); else Query(k<<1|1,mid+1,r,x);
    }
}
void Insert(int k,int l,int r,int x,int y)
{
    if (l==x && r==y) { que[k].push(A{num,now}); return;    }
    int mid=(l+r)>>1;
    if (y<=mid) Insert(k<<1,l,mid,x,y);
    else if (x>mid) Insert(k<<1|1,mid+1,r,x,y);
    else Insert(k<<1,l,mid,x,mid), Insert(k<<1|1,mid+1,r,mid+1,y);
}
int main()
{
    n=read(), m=read();
    for (int i=1;i<n;++i) x=read(), y=read(), Build(x,y);
    DFS1(1), DFS2(1,1);
    for (now=1;now<=m;++now) 
    {
        op=read();
        if (op==0)
        {
            x=read(), y=read(), num=read(), cnt=0;
            for (;anc[x]!=anc[y];x=fa[anc[x]])
            {
                if (deep[anc[x]]<deep[anc[y]]) swap(x,y);
                a[++cnt].x=pos[anc[x]], a[cnt].y=pos[x];
            }
            if (deep[x]>deep[y]) swap(x,y);
            a[++cnt].x=pos[x], a[cnt].y=pos[y];
            sort(a+1,a+1+cnt);
            for (int i=1;i<=cnt;++i)
                if (a[i-1].y+1<a[i].x) Insert(1,1,n,a[i-1].y+1,a[i].x-1);
            if (a[cnt].y<n) Insert(1,1,n,a[cnt].y+1,n);
        }
        else if (op==1) flag[read()]=1;
        else ans=-1, Query(1,1,n,pos[read()]), printf("%d\n",ans);
    }
    return 0;
}

T3. 树

Description	小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下： （1）将模板树复制为初始的大树。 （2）以下(2.1)(2.2)(2.3)步循环执行M次 （2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。 （2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。 （2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。 下面给出一个实例。假设模板树如下图： 根据第(1)步，初始的大树与模板树是相同的。 在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示 现在他想问你，树中一些结点对的距离是多少。
Input	第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。
Output	输出Q行，每行一个整数，第 i行是第 i个询问的答案。
Sample Input	5 2 3  1 4  1 3  4 2  4 5  4 3  3 2  6 9  1 8  5 3
Sample Output	6 3 3
Hint	经过两次操作后，大树变成了下图所示的形状： 结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。
Data Range

传送门： http://www.lydsy.com/JudgeOnline/problem.php?id=4539

复杂的分类讨论啊

心累。。