Milk Visits G
自己做出来哒！
先考虑是一条链时怎么做。
很显然，用set维护每种奶的位置，然后lowerbound查找\(l\)再判断是否合法即可。
那么再放到树上来做，显然，直接树链剖分就可以把树转化成链。
于是做完力！
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define iter set<int>::iterator
int head[N], nxt[N * 2], to[N * 2], cnt;
int sz[N], top[N], fa[N], son[N], dep[N], dfn[N], tot, nfd[N];
int t[N], tmp[N], n, m;
set<int> s[N];
void add(int x, int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs1(int x, int f){
sz[x] = 1;
nfd[tot] = x;
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(v == f) continue;
dfs1(v,x);
sz[x] += sz[v];
if(sz[son[x]] < sz[v]) son[x] = v;
}
}
void dfs2(int x,int f){
dfn[x] = ++tot;
dep[x] = dep[f] + 1;
fa[x] = f;
if(son[x]){
top[son[x]] = top[x];
dfs2(son[x],x);
}
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(v == f || v == son[x]) continue;
top[v] = v;
dfs2(v,x);
}
}
bool check(int a, int b, int c){
// a = dfn[a], b = dfn[b];
while(top[a] != top[b]){
if(dep[top[a]] < dep[top[b]]) swap(a,b);
// if(s[c].empty)
iter t = s[c].lower_bound(dfn[top[a]]);
// printf("t = %d, %d %d\n",*t, top[a], a);
if(t != s[c].end() && *t <= dfn[a]) return 1;
a = fa[top[a]];
}
if(dep[a] > dep[b]) swap(a,b);
iter t = s[c].lower_bound(dfn[a]);
// printf("t = %d, %d %d\n",*t,dfn[a],dfn[b]);
if(t != s[c].end() && *t <= dfn[b]) return 1;
return 0;
}
void debug(){
printf("top : "); for(int i = 1; i <= n ;i ++) printf("%d ",top[i]); printf("\n");
printf("sz : "); for(int i = 1; i <= n ; i ++) printf("%d ",sz[i]); printf("\n");
printf("dep : ");for(int i = 1; i <= n; i ++) printf("%d ",dep[i]); printf("\n");
printf("fa : ");for(int i = 1; i <= n; i ++) printf("%d ",fa[i]); printf("\n");
printf("son : ");for(int i = 1; i <= n; i ++) printf("%d ",son[i]); printf("\n");
printf("dfn : ");for(int i = 1; i <= n; i ++) printf("%d ",dfn[i]); printf("\n");
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i ++) scanf("%d",&t[i]), tmp[i] = t[i];
// sort(tmp + 1, tmp + n + 1);
// int len = unique(tmp + 1, tmp + n + 1) - tmp;
// for(int i = 1; i <= n; i ++){
// t[i] = lower_bound(tmp + 1, tmp + n + 1, t[i]) - tmp;
// s[t[i]].insert(i);
// }
for(int i = 1,a,b; i <= n - 1; i ++){
scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
dfs1(1,0); dfs2(1,0);
for(int i = 1; i <= n; i ++){
s[t[i]].insert(dfn[i]);
// printf(" %d %d\n", );
}
// for(int i = 1; i <= 2; i ++) printf("%d%")
// debug();
for(int i = 1, a, b, c; i <= m; i ++){
scanf("%d%d%d",&a,&b,&c);
// c = lower_bound()
if(check(a,b,c)) printf("1");
else printf("0");
}
return 0;
}
Trees of Tranquillity
好题啊好题
（怎么做的时候感觉全是史题，整理的时候感觉全是好题qwq）
首先介绍一个概念：欧拉序
其实就是一个另类的dfs序，对于每个点，进入它时盖一个时间戳，离开它时再盖一个时间戳
这个东西有什么用呢？
我们注意到，树上两个点a、b的欧拉序，要么a包含b（或反之），说明a是b的祖先，要么干脆不相交，不会出现部分相交的情况。
那么在这道题里就很有用了啊
在第二棵树上没有祖先关系，也就是说，欧拉序不相交。
那么我们对每个点，维护它在第二颗树上的欧拉序，然后回到第一颗树上，要求a、b在第一棵树上有祖先后代关系，那么我们直接dfs就好了，dfs的同时动态维护一个贪心用的set，进入时更新，离开时回溯，为的是确保它维护的始终是这个点到根节点的链上的信息。
那么问题就转化为：有n个区间，求最多有多少个不交区间。——这显然是个贪心。
具体而言，我们用set维护一个pair，first为进入时的欧拉序，second为点的编号（这样可以轻松找到离开时的欧拉序，如果把second作为离开时的欧拉序，则很难找到点的编号），每次进入时，会产生三种情况：
（1）祖先中有区间包含它。如果两个区间有包含关系，根据贪心，显然选更小的区间更优，也就是说，把祖先踢出去，选当前区间。但注意离开这个点时还要踢掉当前区间，把祖先加回去，记录一下即可。
（2）它包含祖先的某个区间。这个区间显然不优，直接踢掉它
（3）它与祖先区间没有包含关系，直接加入即可。注意离开时要把它踢掉。
那么这道题就做完力
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define iter set< pair<int,int> >::iterator
#define fi first
#define se second
#define pii pair<int,int>
const int N = 3e5 + 5;
int head[N],nxt[N*2],to[N*2],cnt;
int head2[N],nxt2[N*2],to2[N*2],cnt2;
int st[N], ed[N], tot, ans, T, n;
set<pii> s;
void add1(int x, int y){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void add2(int x, int y){
to2[++cnt2] = y;
nxt2[cnt2] = head2[x];
head2[x] = cnt2;
}
void dfs2(int x, int f){
st[x] = ++tot;
for(int i = head2[x]; i; i = nxt2[i]){
int v = to2[i];
if(v == f) continue;
dfs2(v,x);
}
ed[x] = ++tot;
}
int check(int x){
iter t = s.lower_bound({st[x], x});
if(t != s.end() && ed[t->se] <= ed[x]) return -2;
if(t == s.begin()) return -1;
t --;
if(ed[t->se] <= ed[x]) return -1;
else{
s.erase({t->fi,t->se});
return t->se;
}
}
void dfs1(int x, int f){
int res = check(x);
if(res != -2){
s.insert({st[x],x});
}
ans = max(ans,(int)s.size());
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(v == f) continue;
dfs1(v,x);
}
if(res != -2){
s.erase({st[x],x});
if(res != -1){
s.insert({st[res],res});
}
}
}
void init(){
s.clear();
for(int i = 1; i <= n ; i ++){
head[i] = head2[i] = 0;
}
cnt = cnt2 = 0;
ans = 0;
tot = 0;
}
void debug(){
for(auto i = 1; i <= n ; i ++){
printf("%d %d %d\n",i, st[i],ed[i]);
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 2, a; i <= n; i ++) scanf("%d",&a), add1(i,a), add1(a,i);
for(int i = 2, b; i <= n; i ++) scanf("%d",&b), add2(i,b), add2(b,i);
dfs2(1,1);
// debug();
dfs1(1,0);
printf("%d\n",ans);
init();
}
}
DFS Trees
第二遍做了，但还只是知其然不知所以然，我还是太菜了。
先跑一边最小生成树，把树边标记出来。
那么对于非树边，它要么是返祖边，要么是横叉边（无向图严格来讲不存在横叉边，大家感性理解下），这两种边是可以随着树根的不同而互相转化的（你自己画个图试试）。
对于所有的“横叉边”，我们dfs到它的时候发现题目中的算法肯定会走这条边，那么得出的最小生成树就是错误的。而返祖边则没有这个问题。
那么对于横叉边，我们考虑它在什么情况下会转化为返祖边。
我们发现只有以两边点子树中的点为根的时候，它才是返祖边。
那么再考虑对于一个点，只有所有非树边对它而言都是返祖边是它才能作为合法根。
那么我们用树上差分，枚举每条非树边，将两边的子树全部加一，最后统计每个点的点权，若等于非树边条数就可以作为根，否则不可以。
注意这里有个特殊情况，即非树边链接的两个点是祖先后代关系，此时只有从u的儿子（是v祖先的那个）到v是不合法的，其它全部合法，因此我们还需要倍增地跳一下fa来确定v到底在哪个儿子里。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int M = 2e5 + 5;
int head[N], nxt[N * 2], to[N * 2], w[N * 2], cnt;
int f[N][25], dep[N], dis[N], s[N], ans[N];
int fa[N];
int n, m;
struct node{
int a, b, w, p;
friend bool operator < (node a, node b){
return a.w < b.w;
}
};
node e[M];
void add(int x, int y, int z){
to[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
w[cnt] = z;
}
void dfs(int x, int fa){
f[x][0] = fa;
dep[x] = dep[fa] + 1;
for(int u = 1; u <= 20; u ++){
f[x][u] = f[f[x][u - 1]][u - 1];
}
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(v == fa) continue;
dis[v] = dis[x] + w[i];
dfs(v,x);
}
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void kruskal(){
sort(e + 1, e + m + 1);
for(int i = 1; i <= m; i ++){
int x = e[i].a, y = e[i].b;
int r1 = find(x), r2 = find(y);
if(r1 == r2) continue;
fa[r1] = r2;
e[i].p = 1;
add(x,y,e[i].w), add(y,x,e[i].w);
}
}
int lca(int x, int y){
if(dep[x] < dep[y]) swap(x,y);
for(int i = 20; i >= 0; i --){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
}
if(x == y) return x;
for(int i = 20; i >= 0; i --){
if(f[x][i] != f[y][i]){
x = f[x][i], y = f[y][i];
}
}
return f[x][0];
}
void dfs1(int x, int f){
ans[x] = ans[f] + s[x];
for(int i = head[x]; i; i = nxt[i]){
int v = to[i];
if(v == f) continue;
// printf(" %d %d\n",x,v);
dfs1(v,x);
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i = 1,a,b; i <= m ; i++){
scanf("%lld%lld",&a,&b);
e[i] = {a,b,i};
fa[i] = i;
}
kruskal();
dfs(1,0);
for(int i = 1; i <= m ; i ++){
if(e[i].p) continue;
int k = lca(e[i].a,e[i].b);
if(k != e[i].a && k != e[i].b) s[e[i].a] ++, s[e[i].b] ++;
else{
if(dep[e[i].a] < dep[e[i].b]) swap(e[i].a, e[i].b);
int x = e[i].a;
for(int u = 20; u >= 0; u --){
if(dis[f[x][u]] > dis[e[i].b]) x = f[x][u];
}
s[1] ++;
s[e[i].a] ++;
s[x] --;
}
}
dfs1(1,0);
for(int i = 1; i <= n ; i ++) printf("%d",ans[i] == m - n + 1);
return 0;
}
消防
我们先考虑只有一个点的情况。任选一个点，到它距离最远的点肯定是直径的一个端点。
直径的两个端点，那么我们考虑任意一个点，到这两个点的最大距离。这个距离显然不小于直径的一半。等于直径的一半时，这个点是直径的中点。
那么再考虑把扩展这个点。如果扩展时不上直径上，显然是没有用的，因为它对最大值不会产生任何影响。
我们如果想缩短这个最大值，就必须在直径上扩展。
因此我们得出结论：最优的路径一定在直径上。
所以处理出直径上的所有点与到它最远且不是直径端点的点之间的距离，在直径