`#include[HTML_REMOVED]
//tarjan 离线求lca O（n + m)
/
在深度优先遍历时，将所有点分成三大类：
[1]已经遍历过，且回溯过的点 并查集合并
[2]正在搜索的搜索的分支
[3]还未搜索到的点
/
//小trick：处理两点之间的距离，可以先通过处理到原点距离来实现
//此处就可以视为d(x) + d(y) - 2 * d(lca)
using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int N = 1e6 + 10;
const int M = 2 * N;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int h[N],e[M],w[M],ne[M],idx;
int p[N];
int res[N];
int st[N];
int dist[N];//每个点和一号点的距离
vector[HTML_REMOVED]query[N];//first存查询的另外一个点,second存查询编号
void dfs(int u,int fa)
{
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
dist[j] = dist[u] + w[i];
dfs(j,u);
}
}
void add(int a,int b,int c)
{
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void tarjan(int u)
{
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(!st[j])
{
tarjan(j);
p[j] = u;
}
}

for(auto item : query[u])
{
    int y = item.first,id = item.second;
    if(st[y] == 2)//已经递归过
    {
        int anc = find(y);
        res[id] = dist[u] + dist[y] - dist[anc] * 2;
    }
}
st[u] = 2;

}
void solve()
{
scanf(“%d%d”,&n,&m);
memset(h,-1,sizeof h);
for(int i = 0; i < n - 1; i ++)
{
int a,b,c;
scanf(“%d%d%d”,&a,&b,&c);
add(a,b,c),add(b,a,c);
}

for(int i = 0; i < m; i ++)
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a != b) 
    {
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }

}
for (int i = 1; i <= n; i ++ )p[i] = i;
dfs(1,-1);
tarjan(1);
for(int i = 0; i < m; i ++) printf("%d\n",res[i]);

return ;

}
int main()
{
solve();

system("pause");
return 0;

}`

`#include[HTML_REMOVED]

using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int N = 35;
const int M = 2 * N;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;
int l,r,a,b;
int f[N][N];//当前位置，已经有多少个0/1/2/3/4/5/6/7/8/9
vector[HTML_REMOVED]nums;

int dfs(int pos,int x,int pre,int lead,int limit)
{
if(pos == -1) return pre;
if(!lead && !limit && ~f[pos][pre]) return f[pos][pre];
int up = limit ? nums[pos]: 9;
int res = 0;
for(int i = 0; i <= up; i ++)
{
res += dfs(pos - 1,x,pre + ((i == x) && !(lead && !i)),lead && !i,limit && i == up);
}
if(!limit && !lead) f[pos][pre] = res;
else return res;

}
int init(int x,int y){
nums.clear();
while(x) nums.push_back(x % 10), x /= 10;
return dfs(nums.size() - 1,y,0,1,1);
}
void solve()
{
while(~scanf(“%d%d”,&l,&r) &&(l || r))
{
if(r < l) swap(l,r);
for(int i = 0; i <= 9; i ++)
{
memset(f,-1,sizeof f);
printf(“%d “,init(r,i)-init(l-1,i));
}
puts(“”);
}
}
int main()
{

solve();



system("pause");
return 0;

}
`#include[HTML_REMOVED]

using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int M = 1e5 + 10,N = 510;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];

void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a],h[a] = idx ++;
}
bool find(int x)
{
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf(“%d%d%d”,&n1,&n2,&m);

memset(h, -1, sizeof h);
while(m --)
{
    int a,b;
    scanf("%d%d",&a,&b);
    add(a,b);
}
int res = 0;
for(int i = 1; i <= n1; i ++)
{
    memset(st,false, sizeof st);//保证每个妹子都没有被男孩子考虑过
    if(find(i))res ++;
}
printf("%d\n",res);


system("pause");
return 0;

}

include[HTML_REMOVED]

using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int N = 1010;
const int M = 2 * N;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int v[N],w[N];
int f[N][N];
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ) cin >> v[i] >> w[i];
for(int i = n; i >= 1; i –)
{
for(int j = 0; j <= m; j )
{
f[i][j] = f[i + 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i + 1][j - v[i]] + w[i]);
}
}
int j = m;
for(int i = 1; i <= n; i ++)
{
if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
{
cout << i << ‘ ‘;
j -= v[i];
}
else continue;
}

}
int main()
{

solve();



system("pause");
return 0;

}
#include[HTML_REMOVED]

using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
int p[N];
struct edge
{
int a,b,w;
bool operator<(const edge & W)const{
return w < W.w;
}
}edges[N];

int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
else return x;
}
int main()
{
scanf(“%d%d”,&n,&m);
for(int i = 0; i < m; i )
{
int a,b,w;
scanf(“%d%d%d”,&a,&b,&w);
edges[i] = {a,b,w};
}
sort(edges,edges + m);
int res = 0,cnt = 0;//res存的是最小生成树的总长，cnt的多少条边
for(int i = 1; i <= n; i ) p[i] = i;

for(int i = 0; i < m; i ++)
{
    int a = edges[i].a,b = edges[i].b,w = edges[i].w;
    a = find(a),b = find(b);
    if(a != b)
    {
        p[a] = b;
        res += w;
        cnt ++;
    }
}
if(cnt < n - 1) puts("impossible");
else 
{
    printf("%d\n",res);
}
system("pause");
return 0;

}
using namespace std;

const int N = 50010;

int p[N],d[N];
int n,m;
void init(int n)
{
for(int i = 1; i <= n; i ++) p[i] = i;
}

int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
} //如果直接更新的话会跳
return p[x];
}

int main()
{
cin >> n >> m;

init(n);

int res = 0;

while(m –)
{
int t,x,y;
scanf(“%d%d%d”,&t,&x,&y);

if(x > n || y > n) res ++;
else 
{
    int px = find(x),py = find(y);
    if(t == 1)
    {
        if(px == py && (d[x] - d[y]) % 3) res ++;
        else if(px != py)
        {
            p[px] = py;
            d[px] = d[y] - d[x];
        }
    }
    else
    {
        if(px == py && (d[x] - d[y] - 1) % 3) res++;
        else if(px != py)
        {
                p[px] = py;
                d[px] = d[y] + 1 - d[x];
        }
    }
}

}
cout<<res<<endl;

system(“pause”);
return 0;
#include[HTML_REMOVED]

using namespace std;

define ll long long

define PII pair[HTML_REMOVED]

define PLL pair[HTML_REMOVED]

const int N = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const double eps = 1e-8;

int n,m;
double a[N][N];
int gauss()
{
int c,r;//c列r行
for(c = 0,r = 0; c < n; c )
{
int t = r;
for(int i = r; i < n; i )
if(fabs(a[i][c]) > fabs(a[t][c]))
t = i;//1.找到绝对值最大的那一行
if(fabs(a[t][c])< eps) continue;

    for(int i = c; i <= n; i ++) swap(a[t][i],a[r][i]);//2.将该行换到最上边（未固定的）
    for(int i = n; i >= c; i --) a[r][i] /= a[r][c];//3.将该行第一个数变成1,倒着

    for(int i = r + 1; i < n; i ++)
        if(fabs(a[i][c]) > eps)
            for(int j = n; j >= c;j --)
                a[i][j] -= a[r][j] * a[i][c];
    r ++;
}
    if(r < n)
    {
        for(int i = r; i < n; i ++)
            if(fabs(a[i][n]) > eps)
            return 2;
        return 1;
    }
    for(int i = n - 1; i >= 0; i --)
    {
        for(int j = i + 1;j < n; j ++)
        {
            a[i][n] -= a[i][j] * a[j][n];//里边会有许多为0的东东就当没看见，把第一行归零
        }
    }//处理最后得出的答案
    return 0;

}
int main()
{
cin >> n;
for(int i = 0; i < n; i )
{
for(int j = 0; j < n + 1; j )
{
cin >> a[i][j];
}
}
int t = gauss();
if (t == 2) puts(“No solution”);
else if (t == 1) puts(“Infinite group solutions”);
else
{
for (int i = 0; i < n; i ++ )
{
if (fabs(a[i][n]) < eps) a[i][n] = 0; // 去掉输出 -0.00 的情况
printf(“%.2lf\n”, a[i][n]);
}
}

return 0;

}
`