今天不宜打数据结构

#include <bits/stdc++.h>
#define endl '\n'

class fastIO {
private:
    char rbuf[100000], wbuf[100000], *p1, *p2, *p3;
    int l, tag;
    inline char get(void) {
        return p1 == p2 && (p2 = (p1 = rbuf) + fread(rbuf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline void put(char x) {
        l == 100000 ? (p3 = wbuf, fwrite(wbuf, 1, 100000, stdout), l = 1, *p3++ = x) : (l++, *p3++ = x);
        return;
    }
public:
    fastIO() : l(0), p1(rbuf), p2(rbuf), p3(wbuf), tag(0) {}
    ~fastIO() {fwrite(wbuf, 1, l, stdout);}
    inline void putLine(const char* x) {
        fwrite(wbuf, 1, l, stdout);
        fwrite(x, 1, strlen(x), stdout);
        l = 0;
        p3 = wbuf;
        return;
    }
    inline void getLine(std::string& x) {
        x.clear();
        char c = get();
        while ((c < 33 || c > 126) && c != EOF) c = get();
        if (c == EOF) tag = 1;
        while ((c >= 33 && c <= 126) || c == ' ') {
            x += c;
            c = get();
        }
        return;
    }
template <typename T>
    inline fastIO& operator >> (T& x) {
        x = 0;
        bool f = 0;
        char c = get();
        while (!isdigit(c) && c != EOF) {
            f |= (c == '-');
            c = get();
        }
        if (c == EOF) tag = 1;
        while (isdigit(c)) {
            x = (x << 1) + (x << 3) + (c ^ 48);
            c = get();
        }
        x = f ? ~x + 1 : x;
        return *this;
    }
    inline fastIO& operator >> (char& x) {
        x = get();
        while ((x < 33 || x > 126) && x != EOF) {
            if (x == EOF) tag = 1;
            x = get();
        }
        return *this;
    }
    inline fastIO& operator >> (std::string& x) {
        x.clear();
        char c = get();
        while ((c < 33 || c > 126) && c != EOF) c = get();
        if (c == EOF) tag = 1;
        while (c >= 33 && c <= 126) {
            x += c;
            c = get();
        }
        return *this;
    }
template <typename Y>
    inline fastIO& operator << (Y x) {
        int putList[25];
        int cnt = 0;
        !x ? (put('0'), 0) : 0;
        x < 0 ? (put('-'), x = ~x + 1) : 0;
        while (x > 0) {
            putList[++cnt] = x % 10 + 48;
            x /= 10;
        }
        while (cnt) put(putList[cnt--]);
        return *this;
    }
    inline fastIO& operator << (char* x) {return putLine(x), *this;}
    inline fastIO& operator << (char x) {return put(x), *this;}
    inline fastIO& operator << (const std::string& x) {return putLine(x.c_str()), *this;}
    inline operator bool() {return tag ? 0 : 1;}
}io;

const int _ = 1e5 + 10;
int dep[_], Size[_], father[_], inTree[_], self[_], v[_], son[_], top[_];
long long p;
std::vector<int> lty[_];

inline void dfs1(int now, int fa, int deep) { //处理点的深度与子树大小 
    dep[now] = deep;
    Size[now] = 1;
    father[now] = fa;//now的father 
    int maxSon = 0;
    for (int i = 0; i < lty[now].size(); i++) {
        if (lty[now][i] == fa) continue;
        dfs1(lty[now][i], now, deep + 1);
        Size[now] += Size[lty[now][i]];
        if (Size[lty[now][i]] > maxSon) {
            son[now] = lty[now][i];
            maxSon = Size[lty[now][i]];
        }
    }
    return;
}

inline void dfs2(int now, int topfather) {
    inTree[now] = ++inTree[0];   //dfs序 
    self[inTree[0]] = v[now];    //新编号对应的值 
    top[now] = topfather;
    if (!son[now]) return;
    dfs2(son[now], topfather);//先走重儿子 
    for (int i = 0; i < lty[now].size(); i++) {
        if (lty[now][i] == father[now] || lty[now][i] == son[now]) continue;
        dfs2(lty[now][i], lty[now][i]);
    }
    return;
}

struct node {//线段树 
    int l, r;
    long long TeRi, lazy;
    node* child[2];
    node(int lty = 0, int yzl = 0) : l(lty), r(yzl), TeRi(0), lazy(0) {
        child[0] = child[1] = NULL;
    }
}*root, point[_ * 2];

inline node* newnode(int lty, int yzl) {
    static int cnt = 0;
    node* o = &point[cnt++];
    o->l = lty;
    o->r = yzl;
    return o;
}