2018.9.21周五

比赛总结

T1

在树上判两条路径是否有相交。
判一对的LCA是否在另一对的路径上。

T2

单调栈 或者 直接bit求左右最小最大值。
首先：统计答案时用所有的最大值的和减去所有的最小值的和。
考虑扫到一个右端点的时候，前面所有作为左端点形成的区间的答案。
x是1~5的最小值，那么1,2,3,4,5~r的最小值就都是x了。所以可以维护一个单调递减的栈，并记录每个值所有覆盖的数，比如x可以覆盖5个数。
o o o o x o o o r
同样的，在记录一个单调栈，递增的，维护最大值。再记录两个变量维护和即可。

T3

启发式合并。

/*
n^2： 
去掉一条边，计算这条边的出现的次数 
比较难计算，正难则反，计算所有的数对-未出现的次数。
所以转化为求一天边未出现在那些数对中：
考虑去掉这条边，然后就成了两个联通块，然后如果l,r中的所有点都在一边，那么就可以去掉。
于是可以求出这些连续的在一边的数字 l,l+1,l+2...r，那么就有(r-l+1)个数这些可以两两组合，可以O(1)算。
nlogn： 
考虑优化。
对于考虑用子树的答案取更新出当前点的答案。
启发式合并。用siz小的子树合并到siz大的，得到整棵树的答案。 
具体见注释。 
*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 100005;
int siz[N], fa[N], son[N], f[N], s[N], n;
int head[N], nxt[N << 1], to[N << 1], En;
LL Sum, Sum2, Answer;
bool vis[N];
set<int>st;
set<int> :: iterator it, it1, it2;
void add_edge(int u,int v) {
    ++En; to[En] = v; nxt[En] = head[u]; head[u] = En;
    ++En; to[En] = u; nxt[En] = head[v]; head[v] = En;
}
void dfs1(int u) {
    siz[u] = 1;
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v == fa[u]) continue;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v];
        if (!son[u] || siz[v] > siz[son[u]]) son[u] = v;
    }
}
int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
} 
inline LL Calc(int x) {
    return (1ll * (x) * (x - 1)) / 2;
}
void add(int x) { // 子树里加一个点（合并的时候，新加一个点） 
    st.insert(x); // 求子树外的答案，加子树内的点。一个点到子树内，就是从子树外拿走了，所以子树外的连续区间就可能断了 
    it1 = it2 = it = st.find(x); it1--, it2 ++; 
    Sum2 -= Calc((*it2) - (*it1) - 1); // 以前的连续区间的长度 
    Sum2 += Calc((*it) - (*it1) - 1) + Calc((*it2) - (*it) - 1); // 这个拿走后
    vis[x] = 1;
    if (vis[x - 1]) { // 和以前的点合并构成新的区间。 
        int u = find(x - 1), v = find(x); 
        Sum += 1ll * s[u] * s[v];
        f[u] = v; s[v] += s[u];
    }
    if (vis[x + 1]) {
        int u = find(x + 1), v = find(x);
        Sum += 1ll * s[u] * s[v];
        f[u] = v; s[v] += s[u];
    }
}
void bfs(int u) {
    add(u);
    for (int i=head[u]; i; i=nxt[i]) 
        if (to[i] != fa[u]) bfs(to[i]);
}
void Clear(int u) {
    s[u] = 1, f[u] = u, vis[u] = 0;
    for (int i=head[u]; i; i=nxt[i]) 
        if (to[i] != fa[u]) Clear(to[i]);
}
void dfs2(int u) {
    for (int i=head[u]; i; i=nxt[i]) {
        int v = to[i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v); // 计算u->v这条边的答案 
        Clear(v); // 清空，防止计算下一个点的时候，产生影响 
        st.clear(), st.insert(0), st.insert(n + 1);
        Sum = 0, Sum2 = Calc(n);
    }
    if (son[u]) dfs2(son[u]); // 最后一次搜索，不清空，st,vis含有son[u]的子树的信息。 
    for (int i=head[u]; i; i=nxt[i]) 
        if (to[i] != fa[u] && to[i] != son[u]) bfs(to[i]);
    add(u);
    Answer += Calc(n) - Sum - Sum2;
}
int main() {
    freopen("treecnt.in","r",stdin);
    freopen("treecnt.out","w",stdout);
    n = read();
    st.clear(), st.insert(0), st.insert(n + 1);
    Sum2 = Calc(n);
    for (int i=1; i<n; ++i) {
        int u = read(), v = read();
        add_edge(u, v);
    }
    dfs1(1);
    for (int i=1; i<=n; ++i) f[i] = i, s[i] = 1;
    dfs2(1);
    cout << Answer;
    return 0;
}