题目链接

CF

题意简述

给你一棵树,每个点的颜色为一个区间内的整数,一种染色方案的权值是所有同色无序点对的距离之和,求所有不同染色方案的权值之和。

点数、颜色数均不超过 $10^5$ 。

简要做法

首先是 $O(n^2)$ 做法:把计算总和转化为计算期望,然后就可以枚举点对,计算同色概率,乘上距离,最后把期望乘上方案数就是答案。进行 $n$ 次 DFS 而不是每次求 LCA 就可以做到 $O(n^2)$ 。

然后是 $O(n\log n\log c)$($c$ 为颜色数)做法:点分治,令 $f(u, v)=\max(0, \min(r_u, r_v)-\max(l_u, l_v)+1)$, 点 $u$ 的贡献是 $\sum_{v}f(u, v)(dep_u+dep_v)(r_u-l_u+1)^{-1}(r_v-l_v+1)^{-1}$,即 $\left(dep_u\cdot(r_u-l_u+1)^{-1}\right)\cdot\left(\sum_{v}f(u, v)(r_v-l_v+1)^{-1}\right)+(r_u-l_u+1)^{-1}\cdot\left(\sum_{v}f(u, v)dep_v(r_v-l_v+1)^{-1}\right)$ ,用以颜色为下标、支持区间加/查询区间和的线段树维护 $\sum_{v}(r_v-l_v+1)^{-1}$ 以及 $\sum_{v}dep_v(r_v-l_v+1)^{-1}$ 即可。

如果你写的是其它 $O(n\log n\log c)$ 做法,如链分治(dsu on tree),或者你的常数比较小(比如使用树状数组而不是线段树),你可能就过了。

否则,你可能 TLE on 6 或者 TLE on 14 之类的。

但是,大常数选手并不是没有活路的,因为这题有 $O(n\log n)$ 做法。

其中一种,是使用差分代替上述做法中的线段树。但如果在点分治内进行比较排序,复杂度是 $O(n\log^2 n)$(尽管瓶颈部分的常数很小),解决方法是在点分治的外部进行一次排序,然后在内部就可以线性地将每棵子树的修改与询问划分开来。

“划分”本质上是一个双关键字排序,第一关键字为所在子树的编号,第二关键字为修改/询问原本的排序方式,利用基数排序的思想,由于第二关键字已经有序,对第一关键字进行稳定排序即可。使用计数排序可以做到线性复杂度,总复杂度就是 $O(n\log n)$ 。

参考代码

nlognlogc
																																																	#ifndef OUUAN
																																																	#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
																																																	#endif
																																																	#include<bits/stdc++.h>
 
//#define int LoveLive
//#define FAST_IOSTREAM 1
 
																																																	#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
																																																	#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
																																																	#define SON(i,u)for(int i=head[u];i;i=nxt[i])
																																																	#define ms(a,x)memset(a,x,sizeof(a))
																																																	#define fi first
																																																	#define se second
																																																	#define pb emplace_back
																																																	#define pq priority_queue
																																																	#define isinf(x)(x>=INF?-1:x)
																																																	#define y1 why_is_there_a_function_called_y1
																																																	#define DEBUG(x)cerr<<(#x)<<":"<<x<<endl
																																																	using namespace std;typedef long long LoveLive;typedef pair<int,int>pii;typedef vector<int>vi;typedef long double ld;const double inf=1e121;const double eps=1e-10;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint(int l,int r){int out=rng()%(r-l+1)+l;return out>=l?out:out+r-l+1;}
																																																	#ifdef int
																																																	const int INF=0x3f3f3f3f3f3f3f3fll;
																																																	#else
																																																	const int INF=0x3f3f3f3f;typedef long long ll;
																																																	#endif
																																																	#ifdef FAST_IOSTREAM
																																																	#define br cout<<'\n'
																																																	#define sp cout<<' '
																																																	long long read(){long long x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename T>void write(const T&x){cout<<x;}
																																																	#else
																																																	#define br putchar('\n')
																																																	#define sp putchar(' ')
																																																	template<typename T>typename enable_if<!is_integral<T>::value,void>::type read(T&x){cin>>x;}long long read(){char c;long long out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double&x){scanf("%lf",&x);return x;}ld read(ld&x){scanf("%Lf",&x);return x;}template<typename T>typename enable_if<!is_integral<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf",x);}void write(const ld&x){printf("%.10Lf",x);}
																																																	#endif
																																																	template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value||(is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){bool isFirst=true;for(;__first!=__last;++__first){if(isFirst)isFirst=false;else sp;write(*__first);}br;}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}template<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template<typename T>void wte(const T&x){write(x);exit(0);}template<typename T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte(const T&x,Args...args){wts(x);wte(args...);}template<typename T>inline bool up(T&x,const T&y){return x<y?x=y,1:0;}template<typename T>inline bool dn(T&x,const T&y){return y<x?x=y,1:0;}template<typename T>inline bool inRange(const T&x,const T&l,const T&r){return!(x<l)&&!(r<x);}template<typename valueType,typename tagType>class segmentTreeNode{public:int id,left,right;valueType val;tagType tag;};template<typename valueType, typename tagType, valueType(*merge)(valueType,valueType), void(*update)(segmentTreeNode<valueType,tagType>&,tagType)>class segmentTree{private:std::vector<segmentTreeNode<valueType,tagType>>nodes;int leftRange,rightRange;valueType valueZero;tagType tagZero;void pushup(int cur){nodes[cur].val=merge(nodes[cur<<1].val,nodes[cur<<1|1].val);}void pushdown(int cur){update(nodes[cur<<1],nodes[cur].tag);update(nodes[cur<<1|1],nodes[cur].tag);nodes[cur].tag=tagZero;}void build(int cur,int l,int r,const std::vector<valueType>&initValue){nodes[cur].id=cur;nodes[cur].left=l;nodes[cur].right=r;nodes[cur].tag=tagZero;if(l==r-1)nodes[cur].val=initValue[l-leftRange];else{build(cur<<1,l,(l+r)>>1,initValue);build(cur<<1|1,(l+r)>>1,r,initValue);pushup(cur);}}void init(const std::vector<valueType>&_initValue,const valueType&_valueZero,const tagType&_tagZero){valueZero=_valueZero;tagZero=_tagZero;nodes.resize((rightRange-leftRange)<<2);build(1,leftRange,rightRange,_initValue);}void modify(int cur,int l,int r,int L,int R,const tagType&tag){if(l>=R||r<=L)return;if(L<=l&&r<=R)update(nodes[cur],tag);else{pushdown(cur);modify(cur<<1,l,(l+r)>>1,L,R,tag);modify(cur<<1|1,(l+r)>>1,r,L,R,tag);pushup(cur);}}valueType query(int cur,int l,int r,int L,int R){if(l>=R||r<=L)return valueZero;if(L<=l&&r<=R)return nodes[cur].val;pushdown(cur);return merge(query(cur<<1,l,(l+r)>>1,L,R), query(cur<<1|1,(l+r)>>1,r,L,R));}public:segmentTree(){}segmentTree(int _leftRange,int _rightRange,const std::vector<valueType>&_initValue,const valueType&_valueZero,const tagType&_tagZero){leftRange=_leftRange;rightRange=_rightRange;init(_initValue,_valueZero,_tagZero);}segmentTree(int size,const std::vector<valueType>&_initValue,const valueType&_valueZero,const tagType&_tagZero){leftRange=1;rightRange=size+1;init(_initValue,_valueZero,_tagZero);}void modify(int l,int r,const tagType&tag){modify(1,leftRange,rightRange,l,r,tag);}void modify(int p,const tagType&tag){modify(p,p+1,tag);}valueType query(int l,int r){return query(1,leftRange,rightRange,l,r);}valueType query(int p){return query(p,p+1);}};class maxFlow{private:typedef long long ll;std::queue<int>q;std::vector<int>head,cur,nxt,to,dep;std::vector<ll>cap;public:maxFlow(int _n=0){init(_n);}void init(int _n){head.clear();head.resize(_n+1,0);nxt.resize(2);to.resize(2);cap.resize(2);}void init(){init(head.size()-1);}void add(int u,int v,ll w){nxt.push_back(head[u]);head[u]=to.size();to.push_back(v);cap.push_back(w);}void Add(int u,int v,ll w){add(u,v,w);add(v,u,0);}void del(int x){cap[x<<1]=cap[x<<1|1]=0;}bool bfs(int s,int t){dep.clear();dep.resize(head.size(),-1);dep[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=nxt[i]){int v=to[i];ll w=cap[i];if(w>0&&dep[v]==-1){dep[v]=dep[u]+1;q.push(v);}}}return ~dep[t];}ll dfs(int u,ll flow,int t){if(dep[u]==dep[t])return u==t?flow:0;ll out=0;for(int&i=cur[u];i;i=nxt[i]){int v=to[i];ll w=cap[i];if(w>0&&dep[v]==dep[u]+1){ll f=dfs(v,std::min(w,flow-out),t);cap[i]-=f;cap[i ^ 1]+=f;out+=f;if(out==flow)return out;}}return out;}ll maxflow(int s,int t){ll out=0;while(bfs(s,t)){cur=head;out+=dfs(s,0x7fffffffffffffffll,t);}return out;}ll getflow(int x)const{return cap[x<<1|1];}};struct customHash{static uint64_t splitmix64(uint64_t x){x+=0x9e3779b97f4a7c15;x=(x ^(x>>30))*0xbf58476d1ce4e5b9;x=(x ^(x>>27))*0x94d049bb133111eb;return x ^(x>>31);}size_t operator()(uint64_t x)const{static const uint64_t FIXED_RANDOM=rng();return splitmix64(x+FIXED_RANDOM);}};
 
typedef pair<bool, pii> pbii;

const int W = 100000;
const int mod = (1e9 + 7//, 998244353
);

vector<vi> g;
vector<bool> vis;
int n, tsiz, rt, ans;
vi l, r, siz, wt, inv;

int qpow(int x, int y)
{
    int out = 1;
    while (y)
    {
        if (y & 1) out = (ll) out * x % mod;
        x = (ll) x * x % mod;
        y >>= 1;
    }
    return out;
}

int modadd(int x, int y)
{
    return (x += y) >= mod ? x - mod : x;
}

pii merge(pii x, pii y)
{
    return pii(modadd(x.fi, y.fi), modadd(x.se, y.se));
}

void update(segmentTreeNode<pii, pbii>& u, pbii x)
{
    if (x.first)
    {
        u.tag = pbii(true, pii(0, 0));
        u.val = pii(0, 0);
    }
    else if (x.se == pii(0, 0)) return;
    u.tag.se = merge(u.tag.se, x.se);
    u.val.fi = (u.val.fi + (ll) x.se.fi * (u.right - u.left)) % mod;
    u.val.se = (u.val.se + (ll) x.se.se * (u.right - u.left)) % mod;
}

segmentTree<pii, pbii, merge, update> t(W, vector<pii>(W, pii(0, 0)), pii(0, 0), pbii(false, pii(0, 0)));

void getroot(int u, int pa)
{
    siz[u] = wt[u] = 1;
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        getroot(v, u);
        siz[u] += siz[v];
        up(wt[u], siz[v]);
    }
    up(wt[u], tsiz - siz[u]);
    if (!rt || wt[u] < wt[rt]) rt = u;
}

void calc(int u, int pa, int dep)
{
    auto res = t.query(l[u], r[u] + 1);
    ans = (ans + (ll) inv[u] * dep % mod * res.fi + (ll) inv[u] * res.se) % mod;
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        calc(v, u, dep + 1);
    }
}

void insert(int u, int pa, int dep)
{
    t.modify(l[u], r[u] + 1, pbii(false, pii(inv[u], (ll) inv[u] * dep % mod)));
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        insert(v, u, dep + 1);
    }
}

void solve(int u)
{
    vis[u] = true;
    t.modify(1, W + 1, pbii(true, pii(0, 0)));
    t.modify(l[u], r[u] + 1, pbii(false, pii(inv[u], 0)));
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        calc(v, u, 1);
        insert(v, u, 1);
    }
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        rt = 0;
        tsiz = siz[v];
        getroot(v, u);
        solve(rt);
    }
}

signed main()
{
    #ifdef FAST_IOSTREAM
    cin.sync_with_stdio(false);
    cin.tie(0);
    #endif

    read(n);

    l.resize(n + 1);
    g.resize(n + 1);
    vis.resize(n + 1, false);
    r = wt = siz = inv = l;

    For (i, 1, n)
    {
        read(l[i], r[i]);
        inv[i] = qpow(r[i] - l[i] + 1, mod - 2);
    }

    For (i, 2, n)
    {
        int u, v;
        read(u, v);
        g[u].pb(v);
        g[v].pb(u);
    }

    tsiz = n;
    getroot(1, 0);
    solve(rt);

    for (int i = 1; i <= n; ++i) ans = (ll) ans * (r[i] - l[i] + 1) % mod;

    cout << ans;

    return 0;
}
nlogn#1
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int qpow(int x, int y)
{
    int out = 1;
    while (y)
    {
        if (y & 1) out = (ll) out * x % mod;
        x = (ll) x * x % mod;
        y >>= 1;
    }
    return out;
}

vector<bool> vis;
int n, tsiz, rt, ans;
vector<vector<int> > g;
vector<int> siz, wt, bel, dep, inv;

struct Modification
{
    int id, p, inv, l;
    Modification(int _id, int _p, int _inv, int _l): id(_id), p(_p), inv(_inv), l(_l) {}
    bool operator<(const Modification& b) const { return p < b.p; }
    int k1() const { return inv; }
    int b1() const { return p == l ? (ll) (1 - l + mod) * k1() % mod : (ll) (mod - p + 1) * k1() % mod; }
    int k2() const { return (ll) inv * dep[id] % mod; }
    int b2() const { return p == l ? (ll) (1 - l + mod) * k2() % mod : (ll) (mod - p + 1) * k2() % mod; }
};

struct Query
{
    int id, p, inv;
    Query(int _id, int _p, int _inv): id(_id), p(_p), inv(_inv) {}
    bool operator<(const Query& b) const { return p < b.p; }
    void calc(int x1, int x2, int type) const { ans = (ans + (ll) type * inv * ((ll) dep[id] * x1 % mod + x2) % mod + mod) % mod; }
};

void getroot(int u, int pa)
{
    siz[u] = wt[u] = 1;
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        getroot(v, u);
        siz[u] += siz[v];
        wt[u] = max(wt[u], siz[v]);
    }
    wt[u] = max(wt[u], tsiz - siz[u]);
    if (!rt || wt[u] < wt[rt]) rt = u;
}

void calc(const vector<Modification>& ms, const vector<Query>& qs, int type)
{
    int k1 = 0, b1 = 0, k2 = 0, b2 = 0, i = 0;
    for (auto q : qs)
    {
        while (i < ms.size() && ms[i].p <= q.p)
        {
            k1 = (k1 + ms[i].k1()) % mod;
            b1 = (b1 + ms[i].b1()) % mod;
            k2 = (k2 + ms[i].k2()) % mod;
            b2 = (b2 + ms[i].b2()) % mod;
            ++i;
        }
        q.calc(((ll) k1 * q.p + b1) % mod, ((ll) k2 * q.p + b2) % mod, type);
    }
}

void dfs(int u, int pa)
{
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        dep[v] = dep[u] + 1;
        bel[v] = bel[u];
        dfs(v, u); 
    }
}

void solve(int u, vector<Modification>& ms, vector<Query>& qs)
{
    vis[u] = true;
    vector<vector<Query> > qson(1, vector<Query>());
    vector<vector<Modification> > mson(1, vector<Modification>());
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        mson.push_back(vector<Modification>());
        qson.push_back(vector<Query>());
        bel[v] = mson.size() - 1;
        dep[v] = 1;
        dfs(v, u);
    }
    bel[u] = dep[u] = 0;
    calc(ms, qs, 1);
    for (auto m : ms) mson[bel[m.id]].push_back(m);
    for (auto q : qs) qson[bel[q.id]].push_back(q);
    vector<Modification>().swap(ms); // free memory, the memory complexity is O(n) instead of O(nlogn) because of these two lines
    vector<Query>().swap(qs);
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        calc(mson[bel[v]], qson[bel[v]], -1);
        tsiz = siz[v];
        rt = 0;
        getroot(v, u);
        solve(rt, mson[bel[v]], qson[bel[v]]);
    }
}

int main()
{
    scanf("%d", &n);

    g.resize(n + 1);
    siz.resize(n + 1, 0);
    vis.resize(n + 1, false);
    wt = bel = dep = inv = siz;

    vector<Modification> ms;
    vector<Query> qs;

    int mul = (mod + 1) / 2;

    for (int i = 1; i <= n; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        mul = (ll) mul * (r - l + 1) % mod;
        inv[i] = qpow(r - l + 1, mod - 2);
        ms.push_back(Modification(i, l, inv[i], l));
        ms.push_back(Modification(i, r + 1, mod - inv[i], l));
        qs.push_back(Query(i, l - 1, mod - inv[i]));
        qs.push_back(Query(i, r, inv[i]));
    }

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    sort(ms.begin(), ms.end());
    sort(qs.begin(), qs.end());

    tsiz = n;
    getroot(1, 0);
    solve(rt, ms, qs);

    cout << (ll) ans * mul % mod;

    return 0;
}
nlogn#2
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

static unsigned fast_mod(uint64_t x)
{
#if !defined(_WIN32) || defined(_WIN64)
    return x % mod;
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.
    unsigned x_high = x >> 32, x_low = (unsigned) x;
    unsigned quot, rem;
    asm("divl %4\n"
        : "=a" (quot), "=d" (rem)
        : "d" (x_high), "a" (x_low), "r" (mod));
    return rem;
}

int modadd(int x, int y)
{
    return (x += y) >= mod ? x - mod : x;
}

int qpow(int x, int y)
{
    int out = 1;
    while (y)
    {
        if (y & 1) out = fast_mod((ll) out * x);
        x = fast_mod((ll) x * x);
        y >>= 1;
    }
    return out;
}

vector<bool> vis;
int n, tsiz, rt, ans;
vector<vector<int> > g;
vector<int> siz, wt, bel, dep, inv, cnt, ma, mb, qa, qb;

struct Modification
{
    int id, p, inv, l;
    Modification(int _id, int _p, int _inv, int _l): id(_id), p(_p), inv(_inv), l(_l) {}
    bool operator<(const Modification& b) const { return p < b.p; }
    int k1() const { return inv; }
    int b1() const { return p == l ? fast_mod((ll) (1 - l + mod) * k1()) : fast_mod((ll) (mod - p + 1) * k1()); }
    int k2() const { return (ll) inv * dep[id] % mod; }
    int b2() const { return p == l ? fast_mod((ll) (1 - l + mod) * k2()) : fast_mod((ll) (mod - p + 1) * k2()); }
};

vector<Modification> ms;

struct Query
{
    int id, p, inv;
    Query(int _id, int _p, int _inv): id(_id), p(_p), inv(_inv) {}
    bool operator<(const Query& b) const { return p < b.p; }
    void calc(int x1, int x2, int type) const { ans = fast_mod(ans + type * fast_mod((ll) inv * (fast_mod((ll) dep[id] * x1 + x2))) + mod); }
};

vector<Query> qs;

void getroot(int u, int pa)
{
    siz[u] = wt[u] = 1;
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        getroot(v, u);
        siz[u] += siz[v];
        wt[u] = max(wt[u], siz[v]);
    }
    wt[u] = max(wt[u], tsiz - siz[u]);
    if (!rt || wt[u] < wt[rt]) rt = u;
}

void calc(int l, int r, int type)
{
    int k1 = 0, b1 = 0, k2 = 0, b2 = 0, i = l;
    for (int j = l; j <= r; ++j)
    {
        Query& q = qs[qa[j]];
        while (i <= r)
        {
            Modification& m = ms[ma[i]];
            if (m.p > q.p) break;
            k1 = modadd(k1, m.k1());
            b1 = modadd(b1, m.b1());
            k2 = modadd(k2, m.k2());
            b2 = modadd(b2, m.b2());
            ++i;
        }
        q.calc(fast_mod((ll) k1 * q.p + b1), fast_mod((ll) k2 * q.p + b2), type);
    }
}

void dfs(int u, int pa)
{
    cnt[bel[u]] += 2;
    for (auto v : g[u])
    {
        if (v == pa || vis[v]) continue;
        dep[v] = dep[u] + 1;
        bel[v] = bel[u];
        dfs(v, u); 
    }
}

void solve(int u, int l, int r)
{
    vis[u] = true;
    int soncnt = bel[u] = dep[u] = 0;
    cnt[0] = l + 1;
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        bel[v] = ++soncnt;
        cnt[bel[v]] = cnt[bel[v] - 1];
        dep[v] = 1;
        dfs(v, u);
    }
    calc(l, r, 1);
    vector<int> cnt2(cnt.begin(), cnt.begin() + soncnt + 1);
    for (int i = r; i >= l; --i) mb[cnt2[bel[ms[ma[i]].id]]--] = ma[i];
    for (int i = l; i <= r; ++i) ma[i] = mb[i];
    for (int i = 0; i <= soncnt; ++i) cnt2[i] = cnt[i];
    for (int i = r; i >= l; --i) qb[cnt2[bel[qs[qa[i]].id]]--] = qa[i];
    for (int i = l; i <= r; ++i) qa[i] = qb[i];
    for (int i = 0; i <= soncnt; ++i) cnt2[i] = cnt[i];
    for (auto v : g[u])
    {
        if (vis[v]) continue;
        calc(cnt2[bel[v] - 1] + 1, cnt2[bel[v]], -1);
        tsiz = siz[v];
        rt = 0;
        getroot(v, u);
        solve(rt, cnt2[bel[v] - 1] + 1, cnt2[bel[v]]);
    }
}

int main()
{
    scanf("%d", &n);

    g.resize(n + 1);
    siz.resize(n + 1, 0);
    vis.resize(n + 1, false);
    wt = bel = dep = inv = cnt = siz;

    int mul = (mod + 1) / 2;

    for (int i = 1; i <= n; ++i)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        mul = fast_mod((ll) mul * (r - l + 1));
        inv[i] = qpow(r - l + 1, mod - 2);
        ms.push_back(Modification(i, l, inv[i], l));
        ms.push_back(Modification(i, r + 1, mod - inv[i], l));
        qs.push_back(Query(i, l - 1, mod - inv[i]));
        qs.push_back(Query(i, r, inv[i]));
    }

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    ma.resize(n * 2);
    mb = qa = qb = ma;
    for (int i = 0; i < n * 2; ++i) ma[i] = qa[i] = i;

    sort(ma.begin(), ma.end(), [](int x, int y) {
        return ms[x] < ms[y];
    });
    sort(qa.begin(), qa.end(), [](int x, int y) {
        return qs[x] < qs[y];
    });

    tsiz = n;
    getroot(1, 0);
    solve(rt, 0, 2 * n - 1);

    cout << fast_mod((ll) ans * mul);

    return 0;
}