苏州建设交通官方网站,筑建网站,出口网站怎么做,WordPress上放广告题目描述 给出一棵树和一个点对集合S#xff0c;多次改变这棵树的形态、在集合中加入或删除点对#xff0c;或询问集合内的每组点对之间的路径是否都经过某条给定边。 输入 输入的第一行包含一个整数 id#xff0c;表示测试数据编号#xff0c;如第一组数据的id1#xff0…题目描述 给出一棵树和一个点对集合S多次改变这棵树的形态、在集合中加入或删除点对或询问集合内的每组点对之间的路径是否都经过某条给定边。 输入 输入的第一行包含一个整数 id表示测试数据编号如第一组数据的id1样例数据的 id 可以忽略。输入的第二行包含两个整数 n,m分别表示图中的点数以及接下来会发生的事件数事件的定义下文中会有描述。初始时 S 为空。接下来 n−1 行每行两个正整数 x,y表示点 x 和点 y 之间有一条无向边。接下来 m 行每行描述一个事件每行的第一个数 type 表示事件的类型。若type1那么接下来有四个正整数x,y,u,v表示先删除连接点x和点y的无向边保证存在这样的无向边然后加入一条连接点u和点v的无向边保证操作后的图仍然满足题中所述条件。若type2那么接下来有两个正整数 x,y表示在 S 中加入点对 (x,y)。若type3那么接下来有一个正整数 x表示删除第 x 个加入 S 中的点对即在第 x 个 type2 的事件中加入 S 中的点对保证这个点对存在且仍然在 S 中。若 type4那么接下来有两个正整数 x,y表示小L询问守在连接点 x 和点 y 的边上是否一定能见到共价大爷保证存在这样的无向边且此时 S 不为空。 输出 对于每个小L的询问输出“YES”或者“NO”均不含引号表示小L一定能或者不一定能见到共价大爷。 样例输入 05 71 21 32 41 52 1 51 1 5 2 54 2 52 1 44 2 53 14 2 4 题解 随机化LCT维护子树信息 对与每个点对随机一个权值把这个权值异或到这两个点上。那么对于查询如果 x 为树根时y 子树中的所有点的权值的异或和等于所有点对的异或和则视为所有点对间的路径都经过 x-y 。别问我怎么想出来的。。。做过一道类似的题 当权值范围足够大时可以近似视为正确。 由于树的形态是变化的因此需要使用LCT维护子树信息具体方法参见这里。 注意维护子树信息的LCTlink时需要makeroot(x),makeroot(y)修改时需要makeroot(x)而不是简单的splay(x)查询时需要先makeroot(x)。 时间复杂度 $O(LCT·n\log n)$ #include cstdio
#include algorithm
#define N 100010
using namespace std;
int fa[N] , c[2][N] , rev[N] , w[N] , sum[N] , vx[N * 3] , vy[N * 3] , vw[N * 3] , tot;
inline void pushup(int x)
{sum[x] sum[c[0][x]] ^ sum[c[1][x]] ^ w[x];
}
inline void pushdown(int x)
{if(rev[x]){int l c[0][x] , r c[1][x];swap(c[0][l] , c[1][l]) , rev[l] ^ 1;swap(c[0][r] , c[1][r]) , rev[r] ^ 1;rev[x] 0;}
}
inline bool isroot(int x)
{return c[0][fa[x]] ! x c[1][fa[x]] ! x;
}
void update(int x)
{if(!isroot(x)) update(fa[x]);pushdown(x);
}
inline void rotate(int x)
{int y fa[x] , z fa[y] , l (c[1][y] x) , r l ^ 1;if(!isroot(y)) c[c[1][z] y][z] x;fa[x] z , fa[y] x , fa[c[r][x]] y , c[l][y] c[r][x] , c[r][x] y;pushup(y) , pushup(x);
}
inline void splay(int x)
{int y , z;update(x);while(!isroot(x)){y fa[x] , z fa[y];if(!isroot(y)){if((c[0][y] x) ^ (c[0][z] y)) rotate(x);else rotate(y);}rotate(x);}
}
inline void access(int x)
{int t 0;while(x) splay(x) , w[x] ^ sum[c[1][x]] ^ sum[t] , c[1][x] t , t x , x fa[x];
}
inline void makeroot(int x)
{access(x) , splay(x) , swap(c[0][x] , c[1][x]) , rev[x] ^ 1;
}
inline void link(int x , int y)
{makeroot(x) , makeroot(y) , fa[x] y , w[y] ^ sum[x] , pushup(y);
}
inline void cut(int x , int y)
{makeroot(x) , access(y) , splay(y) , fa[x] c[0][y] 0 , pushup(y);
}
int main()
{srand(20011011);int n , m , i , opt , x , y , u , v , now 0;scanf(%*d%d%d , n , m);for(i 1 ; i n ; i ) scanf(%d%d , x , y) , link(x , y);while(m -- ){scanf(%d%d , opt , x);if(opt 1) scanf(%d%d%d , y , u , v) , cut(x , y) , link(u , v);else if(opt 2){scanf(%d , y);vx[tot] x , vy[tot] y , vw[tot] (rand() 15) rand() , now ^ vw[tot];makeroot(x) , w[x] ^ vw[tot] , pushup(x);makeroot(y) , w[y] ^ vw[tot] , pushup(y);}else if(opt 3){now ^ vw[x];makeroot(vx[x]) , w[vx[x]] ^ vw[x] , pushup(vx[x]);makeroot(vy[x]) , w[vy[x]] ^ vw[x] , pushup(vy[x]);}else scanf(%d , y) , makeroot(x) , access(y) , splay(y) , puts(sum[x] now ? YES : NO);}return 0;
}转载于:https://www.cnblogs.com/GXZlegend/p/8244009.html
